oj.uz

Submission #253642

# Submission time Handle Problem Language Result Execution time Memory
253642 2020-07-28T13:29:40 Z MrRobot_28 Checker (COCI19_checker) C++17
110 / 110
 1270 ms 52456 KB 
#include<bits/stdc++.h>
 
using namespace std;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
		int n;
		cin >> n;
		string s1;
		cin >> s1;
		map <pair <int, int>, int> mp;
		set <pair <int, int> >st1;
		for(int i = 0; i < n; i++)
		{
			st1.insert({i, (i + 1) % n});
			mp[{i, (i + 1) % n}] = s1[i] - '0';
		}
		set <pair <pair <int, int>, int> > s;
		vector <int> pr(n);
		vector <int> nxt(n);
		for(int i = 0; i < n; i++)
		{
			pr[i] = (i - 1 + n) % n;
			nxt[i] = (i + 1) % n;
		}
		queue <pair <pair <int, int>, int> > st;
		bool flag1 = 1;
		bool flag2 = 1;
		for(int i = 0; i < n - 3; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;
			a--;
			b--;
			if(a == b || pr[a] == b || nxt[a] == b)
			{
				flag1 = 0;
			}
			if(nxt[nxt[a]] == b)
			{
				st.push({{a, b}, c});
			}
			else if(pr[pr[a]] == b)
			{
				st.push({{b, a}, c});
			}
			else
			{
				s.insert({{a, b}, c});
				s.insert({{b, a}, c});
			}
		}
		if(flag1)
		{
			while(st.size() != 0)
			{
				int a = st.front().first.first;
				int b = st.front().first.second;
				int c = st.front().second;
				st.pop();
				if(nxt[nxt[a]] != b || st1.find({a, nxt[a]}) == st1.end() || st1.find({nxt[a], b}) == st1.end())
				{
					flag1 = 0;
					break;
				}
				int kol1 = mp[{a, nxt[a]}];
				int kol2 = mp[{nxt[a], b}];
				if(kol1 == kol2 || kol1 == c || kol2 == c)
				{
					flag2 = 0;
				}
				st1.erase({a, nxt[a]});
				st1.erase({nxt[a], b});
				st1.insert({a, b});
				mp[{a, b}] = c;
				nxt[a] = b;
				pr[b] = a;
				set <pair <pair <int, int>, int> > :: iterator it1, it2;
				it1 = s.lower_bound({{a, nxt[b]}, 0});
				it2 = s.lower_bound({{pr[a], b}, 0});
				if(it1 != s.end() && it1 -> first == make_pair(a, nxt[b]))
				{
					st.push({{a, nxt[b]}, it1 -> second});
					s.erase({{it1 -> first.first, it1 -> first.second}, it1 -> second});
					s.erase({{it1 -> first.second, it1 -> first.first}, it1 -> second});
				}
				if(it2 != s.end() && it2 -> first == make_pair(pr[a], b))
				{
					st.push(*it2);
					s.erase({{it2 -> first.first, it2 -> first.second}, it2 -> second});
					s.erase({{it2 -> first.second, it2 -> first.first}, it2 -> second});
				}
			}
		}
		if(s.size() != 0)
		{
			flag1 = 0;
		}
		if(!flag1)
		{
			cout << "neispravna triangulacija\n";
		}
		else if(!flag2)
		{
			cout << "neispravno bojenje\n";
		}
		else
		{
			cout << "tocno\n";
		}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 46620 KB Output is correct
2 Correct 1196 ms 46956 KB Output is correct
3 Correct 1205 ms 46996 KB Output is correct
4 Correct 1215 ms 47108 KB Output is correct
5 Correct 1156 ms 47108 KB Output is correct
6 Correct 610 ms 52344 KB Output is correct
7 Correct 700 ms 52352 KB Output is correct
8 Correct 470 ms 52356 KB Output is correct
9 Correct 524 ms 52356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 46592 KB Output is correct
2 Correct 1196 ms 47056 KB Output is correct
3 Correct 1211 ms 46896 KB Output is correct
4 Correct 1197 ms 46968 KB Output is correct
5 Correct 1244 ms 46980 KB Output is correct
6 Correct 618 ms 52228 KB Output is correct
7 Correct 709 ms 52228 KB Output is correct
8 Correct 602 ms 52228 KB Output is correct
9 Correct 690 ms 52228 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 1190 ms 46620 KB Output is correct
16 Correct 1196 ms 46956 KB Output is correct
17 Correct 1205 ms 46996 KB Output is correct
18 Correct 1215 ms 47108 KB Output is correct
19 Correct 1156 ms 47108 KB Output is correct
20 Correct 610 ms 52344 KB Output is correct
21 Correct 700 ms 52352 KB Output is correct
22 Correct 470 ms 52356 KB Output is correct
23 Correct 524 ms 52356 KB Output is correct
24 Correct 1197 ms 46592 KB Output is correct
25 Correct 1196 ms 47056 KB Output is correct
26 Correct 1211 ms 46896 KB Output is correct
27 Correct 1197 ms 46968 KB Output is correct
28 Correct 1244 ms 46980 KB Output is correct
29 Correct 618 ms 52228 KB Output is correct
30 Correct 709 ms 52228 KB Output is correct
31 Correct 602 ms 52228 KB Output is correct
32 Correct 690 ms 52228 KB Output is correct
33 Correct 1193 ms 47032 KB Output is correct
34 Correct 1201 ms 46980 KB Output is correct
35 Correct 1270 ms 47236 KB Output is correct
36 Correct 1166 ms 47040 KB Output is correct
37 Correct 1164 ms 46980 KB Output is correct
38 Correct 1182 ms 47088 KB Output is correct
39 Correct 1213 ms 46980 KB Output is correct
40 Correct 617 ms 52356 KB Output is correct
41 Correct 710 ms 52356 KB Output is correct
42 Correct 648 ms 52384 KB Output is correct
43 Correct 619 ms 52456 KB Output is correct