oj.uz

Submission #76468

# Submission time Handle Problem Language Result Execution time Memory
76468 2018-09-13T14:39:44 Z mfbalin Dijamant (COI16_dijament) C++17
100 / 100
 977 ms 131368 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1736 KB Output is correct
3 Correct 4 ms 1736 KB Output is correct
4 Correct 4 ms 1736 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1736 KB Output is correct
3 Correct 4 ms 1736 KB Output is correct
4 Correct 4 ms 1736 KB Output is correct
5 Correct 3 ms 1752 KB Output is correct
6 Correct 7 ms 1816 KB Output is correct
7 Correct 5 ms 1908 KB Output is correct
8 Correct 4 ms 1908 KB Output is correct
9 Correct 4 ms 1908 KB Output is correct
10 Correct 4 ms 1980 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1736 KB Output is correct
3 Correct 4 ms 1736 KB Output is correct
4 Correct 4 ms 1736 KB Output is correct
5 Correct 3 ms 1752 KB Output is correct
6 Correct 7 ms 1816 KB Output is correct
7 Correct 5 ms 1908 KB Output is correct
8 Correct 4 ms 1908 KB Output is correct
9 Correct 4 ms 1908 KB Output is correct
10 Correct 4 ms 1980 KB Output is correct
11 Correct 2 ms 1980 KB Output is correct
12 Correct 4 ms 1980 KB Output is correct
13 Correct 4 ms 1980 KB Output is correct
14 Correct 4 ms 1980 KB Output is correct
15 Correct 4 ms 2008 KB Output is correct
16 Correct 3 ms 2008 KB Output is correct
17 Correct 3 ms 2008 KB Output is correct
18 Correct 7 ms 2060 KB Output is correct
19 Correct 4 ms 2064 KB Output is correct
20 Correct 4 ms 2084 KB Output is correct
21 Correct 4 ms 2092 KB Output is correct
22 Correct 3 ms 2092 KB Output is correct
23 Correct 4 ms 2092 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 127584 KB Output is correct
2 Correct 977 ms 131228 KB Output is correct
3 Correct 208 ms 131228 KB Output is correct
4 Correct 57 ms 131228 KB Output is correct
5 Correct 115 ms 131228 KB Output is correct
6 Correct 200 ms 131364 KB Output is correct
7 Correct 183 ms 131364 KB Output is correct
8 Correct 185 ms 131364 KB Output is correct
9 Correct 175 ms 131364 KB Output is correct
10 Correct 368 ms 131364 KB Output is correct
11 Correct 128 ms 131364 KB Output is correct
12 Correct 769 ms 131368 KB Output is correct