oj.uz

Submission #227320

# Submission time Handle Problem Language Result Execution time Memory
227320 2020-04-26T22:37:31 Z abeker Checker (COCI19_checker) C++17
110 / 110
 1071 ms 76000 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int MAXN = 2e5 + 5;

int N;
char sides[MAXN];
vector <pii> adj[MAXN];
map <pii, int> clr;

void add_edge(int a, int b, int c) {
	adj[a].push_back({b, c});
	adj[b].push_back({a, c});
	clr[{a, b}] = clr[{b, a}] = c;
}

void load() {
	scanf("%*d%d%s", &N, sides);
	for (int i = 0; i < N; i++)
		add_edge(i, (i + 1) % N, sides[i] - '0');
	for (int i = 0; i < N - 3; i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		add_edge(--x, --y, c);
	}
}

void solve() {
	bool coloring = true;
	for (int i = 0; i < N; i++) {
		sort(adj[i].begin(), adj[i].end());
		auto it = lower_bound(adj[i].begin(), adj[i].end(), pii(i, 0));
		if (it == adj[i].end())
			it = adj[i].begin();
		rotate(adj[i].begin(), it, adj[i].end());
		for (int j = 1; j < adj[i].size(); j++) {
			pii x = adj[i][j - 1], y = adj[i][j];
			int tmp = clr[{x.first, y.first}];
			if (!tmp) {
				puts("neispravna triangulacija");
				return;
			}
			coloring &= tmp != x.second && tmp != y.second && x.second != y.second;
		}
	}
	puts(coloring ? "tocno" : "neispravno bojenje");
}

int main() {
	load();
	solve();
	return 0;
}

Compilation message

checker.cpp: In function 'void solve()':
checker.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < adj[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
checker.cpp: In function 'void load()':
checker.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%*d%d%s", &N, sides);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
checker.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 12 ms 5760 KB Output is correct
9 Correct 10 ms 5632 KB Output is correct
10 Correct 10 ms 5760 KB Output is correct
11 Correct 10 ms 5760 KB Output is correct
12 Correct 12 ms 5760 KB Output is correct
13 Correct 10 ms 5632 KB Output is correct
14 Correct 11 ms 5632 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 74732 KB Output is correct
2 Correct 826 ms 74680 KB Output is correct
3 Correct 689 ms 74408 KB Output is correct
4 Correct 852 ms 74712 KB Output is correct
5 Correct 721 ms 74728 KB Output is correct
6 Correct 947 ms 75832 KB Output is correct
7 Correct 988 ms 75880 KB Output is correct
8 Correct 759 ms 75880 KB Output is correct
9 Correct 751 ms 75872 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 74572 KB Output is correct
2 Correct 825 ms 74616 KB Output is correct
3 Correct 839 ms 74448 KB Output is correct
4 Correct 817 ms 74744 KB Output is correct
5 Correct 815 ms 74488 KB Output is correct
6 Correct 986 ms 75868 KB Output is correct
7 Correct 1071 ms 76000 KB Output is correct
8 Correct 950 ms 75868 KB Output is correct
9 Correct 907 ms 75872 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 12 ms 5760 KB Output is correct
9 Correct 10 ms 5632 KB Output is correct
10 Correct 10 ms 5760 KB Output is correct
11 Correct 10 ms 5760 KB Output is correct
12 Correct 12 ms 5760 KB Output is correct
13 Correct 10 ms 5632 KB Output is correct
14 Correct 11 ms 5632 KB Output is correct
15 Correct 900 ms 74732 KB Output is correct
16 Correct 826 ms 74680 KB Output is correct
17 Correct 689 ms 74408 KB Output is correct
18 Correct 852 ms 74712 KB Output is correct
19 Correct 721 ms 74728 KB Output is correct
20 Correct 947 ms 75832 KB Output is correct
21 Correct 988 ms 75880 KB Output is correct
22 Correct 759 ms 75880 KB Output is correct
23 Correct 751 ms 75872 KB Output is correct
24 Correct 860 ms 74572 KB Output is correct
25 Correct 825 ms 74616 KB Output is correct
26 Correct 839 ms 74448 KB Output is correct
27 Correct 817 ms 74744 KB Output is correct
28 Correct 815 ms 74488 KB Output is correct
29 Correct 986 ms 75868 KB Output is correct
30 Correct 1071 ms 76000 KB Output is correct
31 Correct 950 ms 75868 KB Output is correct
32 Correct 907 ms 75872 KB Output is correct
33 Correct 826 ms 74752 KB Output is correct
34 Correct 846 ms 74740 KB Output is correct
35 Correct 751 ms 74552 KB Output is correct
36 Correct 757 ms 74616 KB Output is correct
37 Correct 816 ms 74412 KB Output is correct
38 Correct 993 ms 74616 KB Output is correct
39 Correct 949 ms 74744 KB Output is correct
40 Correct 1028 ms 75868 KB Output is correct
41 Correct 896 ms 75956 KB Output is correct
42 Correct 749 ms 75832 KB Output is correct
43 Correct 883 ms 75744 KB Output is correct