Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 9/9 3,266 MiB 0,000 s OK
#2 9/9 3,266 MiB 0,000 s OK
#3 9/9 3,051 MiB 0,004 s OK
#4 9/9 3,266 MiB 0,000 s OK
#5 9/9 3,063 MiB 0,000 s OK
#6 9/9 3,137 MiB 0,010 s OK
#7 9/9 3,668 MiB 0,021 s OK
#8 9/9 3,781 MiB 0,010 s OK
#9 9/9 3,727 MiB 0,016 s OK
#10 9/9 5,961 MiB 0,045 s OK
#11 10/10 3,055 MiB 0,000 s OK

Ocenjevani program (Source.cpp):
#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> split(string s, string d) {
	vector<string> res;
	size_t pos = 0, last = 0;
	while ((pos = s.find(d, last + 1)) != string::npos) {
		res.push_back(s.substr(last, pos - last));
		last = pos + 1;
	}
	res.push_back(s.substr(last));
	return res;
}

vector<int> splitIndices(string s, string d) {
	vector<int> indices;
	size_t pos = 0, last = 0;
	while ((pos = s.find(d, last + 1)) != string::npos) {
		indices.push_back(stoi(s.substr(last, pos - last)) - 1);
		last = pos + 1;
	}
	indices.push_back(stoi(s.substr(last)) - 1);
	return indices;
}

struct birokrat {
	public:
		string name;
		string longName;
		string blame;
		bool visited = false;
		birokrat(string n, string ln, string b) {
			name = n;
			longName = ln;
			blame = b;
		}
};

class Node {
	public:
		string name;
		vector<birokrat> birokrati;
		vector<Node> subnodes;
};

birokrat* findFirst(Node* ptr) {
	if (ptr->birokrati.size() > 0) return &(ptr->birokrati[0]);
	return findFirst(&(ptr->subnodes[0]));
}

int main() {
	string nm, bl;
	int count = 0;
	
	Node root;
	root.name = "";
	Node* ptr = &root;

	while (cin >> nm >> bl) {
		vector<string> splt = split(nm.substr(1), "/");
		int pos = 0;
		while (pos < (int)splt.size() - 1) {
			string s = splt[pos];
			int i;
			for (i = 0; i < ptr->subnodes.size(); ++i) {
				if (ptr->subnodes[i].name >= s) {
					break;
				}
			}
			if (i == ptr->subnodes.size() || ptr->subnodes[i].name != s) {
				ptr->subnodes.insert(ptr->subnodes.begin() + i, Node());
				ptr->subnodes[i].name = s;
			}
			ptr = &(ptr->subnodes[i]);
			++pos;
		}
		int j = 0;
		for (j = 0; j < ptr->birokrati.size(); ++j) {
			if (ptr->birokrati[j].name > splt[pos]) {
				break;
			}
		}
		ptr->birokrati.insert(ptr->birokrati.begin() + j, birokrat(splt[pos], nm, bl));
		ptr = &root;
	}

	bool fault = false;
	string fag;
	
	birokrat* b = findFirst(&root);
	b->visited = true;

	while (!fault) {
		vector<int> indices = splitIndices(b->blame, ".");
		int pos = 0;
		while (pos < indices.size() - 1) {
			if (indices[pos] < ptr->subnodes.size()) {
				ptr = &(ptr->subnodes[indices[pos]]);
			} else {
				fault = true;
				fag = b->longName;
				break;
			}
			++pos;
		}

		if (indices[pos] < ptr->birokrati.size() && !ptr->birokrati[indices[pos]].visited) {
			b = &(ptr->birokrati[indices[pos]]);
			b->visited = true;
		} else {
			fag = b->longName;
			fault = true;
		}
		if (fault) break;
		ptr = &root;
	}

	cout << fag << endl;

	//system("pause");
	return 0;
}