Submission #76468

#	Time	Username	Problem	Language	Result	Execution time	Memory
76468		mfbalin	Dijamant (COI16_dijament)	C++17	100 / 100	977 ms	131368 KiB

dijament

#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#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<bitset<1000>> derived(N);
	vector<vector<bitset<1000>>> inter(N, vector<bitset<1000>>(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]);
		bitset<1000> derivedtemp;
		for(auto i: dd) {
			derivedtemp |= derived[i];
			derivedtemp[i] = true;
		}
		vector<int> ttt;
		for(int j = 0; j < 1000; j++)
			if(derivedtemp[j])
				ttt.push_back(j);
		for(int jj = 0; jj < ttt.size(); jj++) {
			int j = ttt[jj];
			for(int kk = jj + 1; kk < ttt.size(); kk++) {
				int k = ttt[kk];
				if(derived[j][k] == false && derived[k][j] == false && inter[j][k].count() > 0) {
					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++)
			inter[i][k] = derived[i] & derived[k];
		cout << "ok\n";
	}
	
	return 0;
}

Compilation message (stderr)

dijament.cpp: In function 'int main(int, char**)':
dijament.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj = 0; jj < ttt.size(); jj++) {
                   ~~~^~~~~~~~~~~~
dijament.cpp:57:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int kk = jj + 1; kk < ttt.size(); kk++) {
                         ~~~^~~~~~~~~~~~

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