Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ASMx64-2018 Birokrati C++ 100/100OK 04. okt '18 @ 18:11

Test Točke Porabljen spomin Porabljen čas Status
#1 9/9 3,289 MiB 0,000 s OK
#2 9/9 3,289 MiB 0,000 s OK
#3 9/9 3,289 MiB 0,000 s OK
#4 9/9 3,074 MiB 0,000 s OK
#5 9/9 3,082 MiB 0,000 s OK
#6 9/9 3,160 MiB 0,004 s OK
#7 9/9 3,563 MiB 0,021 s OK
#8 9/9 3,836 MiB 0,022 s OK
#9 9/9 3,574 MiB 0,010 s OK
#10 9/9 5,887 MiB 0,033 s OK
#11 10/10 3,070 MiB 0,004 s OK

Ocenjevani program (birokrati2.cpp):
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
#define CSIZE 256

struct oseba {
	oseba(string &ime) : ime(ime), obiskano(false) {}
	bool operator<(const oseba& b) { return ime < b.ime; }
	int stevilka;
	string ime;
	vector<int> poslje;
	string fullName;
	bool obiskano;
};

struct oddelek {
	oddelek() {}
	oddelek(string &ime) : ime(ime), stevilka(0) {}
	bool operator< ( const oddelek &b) { return ime < b.ime; }
	string ime;
	int stevilka;
	vector<oddelek> pododdelek;
	vector<oseba> osebe;
};

oddelek odd;
oseba* minOs;
vector<int> minVec;
bool minSet = false;

bool manjse(vector<int> &a, vector<int> &b) {
	int mm = min(a.size(), b.size());
	for (int i = 0; i < mm; ++i) {
		if (a[i] < b[i])
			return true;
		if (b[i] < a[i])
			return false;
	}
	return a.size() < b.size();
}


int findOddelekInt(vector<oddelek> &arr, int st){
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i].stevilka == st)
			return i;
	}
	return -1;
}

int findOddelekString(vector<oddelek> &arr, string &s) {
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i].ime == s)
			return i;
	}
	return -1;
}

int findImeInt(vector<oseba> &arr, int st) {
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i].stevilka == st)
			return i;
	}
	return -1;
}
int findImeString(vector<oseba> &arr, string s) {
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i].ime == s)
			return i;
	}
	return -1;
}

oseba* insertInto(vector<string> pot, string &fullPath) {
	oddelek * curr = &odd;

	for (int i = 0; i < pot.size() - 1; ++i) {
		int index = findOddelekString(curr->pododdelek, pot[i]);
		if (index == -1) {
			curr->pododdelek.emplace_back(pot[i]);
			curr = &curr->pododdelek.back();
		}
		else
			curr = &curr->pododdelek[index];
	}

	curr->osebe.emplace_back(pot.back());
	curr->osebe.back().fullName = fullPath;
	return &curr->osebe.back();
}

oseba* find(vector<int> &num) {
	oddelek * curr = &odd;

	for (int i = 0; i < num.size() - 1; ++i) {
		int index = findOddelekInt(curr->pododdelek, num[i]);
		if (index == -1) {
			return nullptr;
		}
		curr = &curr->pododdelek[index];
	}

	int index = findImeInt(curr->osebe, num.back());
	if (index == -1) return nullptr;
	return &curr->osebe[index];
}

vector<string> parseName(string &input) {
	vector<string> rez;
	int nivo = 0;
	string s;

	for (int i = 1; i <input.size(); ++i) {
		if (input[i] == '/') {
			rez.emplace_back(s);
			s.clear();
		}
		else {
			s.push_back(input[i]);
		}
	}
	rez.emplace_back(s);
	return rez;
}

void setPosiljanje(oseba* os, string &pos) {
	int num = 0;
	for (int i = 0; i < pos.size(); ++i) {
		if (pos[i] == '.') {
			os->poslje.emplace_back(num);
			num = 0;
		}
		else {
			num = 10 * num + (pos[i] - '0');
		}
	}

	if (pos.back() != '.')
		os->poslje.emplace_back(num);
}

vector<int> tempSt;
void rek(oddelek* curr) {
	if (curr != &odd) {
		tempSt.push_back(curr->stevilka);
	}

	sort(curr->pododdelek.begin(), curr->pododdelek.end());
	for (int i = 0; i < curr->pododdelek.size(); ++i)
		curr->pododdelek[i].stevilka = i + 1;

	sort(curr->osebe.begin(), curr->osebe.end());
	for (int i = 0; i < curr->osebe.size(); ++i) {
		curr->osebe[i].stevilka = i + 1;
		tempSt.push_back(curr->osebe[i].stevilka);

		if (!minSet) {
			minOs = &curr->osebe[i];
			minVec = tempSt;
			minSet = true;
		}
		else if(manjse(tempSt, minVec)){
			minOs = &curr->osebe[i];
			minVec = tempSt;
		}
		tempSt.pop_back();
	}

	for (int i = 0; i < curr->pododdelek.size(); ++i) {
		rek(&curr->pododdelek[i]);
	}
	if (curr != &odd) {
		tempSt.pop_back();
	}
	
}

int main() {
	string pos;
	string str;
	oseba* os;
	while (!cin.eof()) {
		cin >> str;
		if (cin.eof()) break;
		cin >> pos;

		os = insertInto(parseName(str), str);
		setPosiljanje(os, pos);
		//setPosiljanje(os[Ssize], pos);
	}

	rek(&odd);

	oseba* curr = minOs, *tt;
	while (true) {
		curr->obiskano = true;
		 tt = find(curr->poslje);
		if (tt == nullptr || (tt && tt->obiskano)) {
			cout << curr->fullName;
			return 0;
		}
		curr = tt;
	}
	
	return 0;
}