Submission #76421

#	Time	Username	Problem	Language	Result	Execution time	Memory
76421		mfbalin	Dijamant (COI16_dijament)	C++11	56 / 100	2082 ms	380248 KiB

dijament

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
int main(int argc, char *argv[]) {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	map<string, int> mp;
	vector<set<int>> derived(N);
	vector<vector<set<int>>> inter(N, vector<set<int>>(N));
	int cnt = 0;
	for(int i = 0; i < N; i++) {
		string K, temp;
		cin >> K >> temp;
		vector<string> DD;
		for(;;) {
			cin >> temp;
			if(temp == ";")
				break;
			DD.push_back(temp);
		}
		/*cerr << K << '\n';
		for(auto &s: DD)
			cerr << s << ' ';
		cerr << endl;*/
		if(mp.find(K) != mp.end()) {
			cout << "greska\n";
			continue;
		}
		bool b = false;
		for(auto &i: DD)
			if(mp.find(i) == mp.end())
				b = true;
		if(b) {
			cout << "greska\n";
			continue;
		}
		mp[K] = cnt++;
		int k = mp[K];
		vector<int> dd;
		for(auto &i: DD)
			dd.push_back(mp[i]);
		set<int> derivedtemp;
		for(auto i: dd) {
			derivedtemp.insert(derived[i].begin(), derived[i].end());
			derivedtemp.insert(i);
		}
		for(auto j: derivedtemp) {
			for(auto k: derivedtemp)
				if(j < k && derived[j].find(k) == derived[j].end() && derived[k].find(j) == derived[k].end() && not inter[j][k].empty()) {
					b = true;
					break;
				}
			if(b)
				break;
		}
		if(b) {
			mp.erase(K);
			cout << "greska\n";
			continue;
		}
		derived[k] = derivedtemp;
		for(int i = 0; i < k; i++) {
			int a = i;
			int b = k;
			if(derived[a].size() > derived[b].size())
				swap(a, b);
			for(auto j: derived[a])
				if(derived[b].find(j) != derived[b].end())
					inter[i][k].insert(j);
		}
		cout << "ok\n";
	}
	
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 0 / 44