# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
520110 | 2022-01-28T12:22:45 Z | tjd229 | Game (IOI14_game) | C++14 | 408 ms | 25104 KB |
#include "game.h" int n; int p[1500]; int mat[1500][1500]; int sz[1500]; int find(int a) { if (p[a] != a) p[a] = find(p[a]); return p[a]; } bool dsu(int a, int b) { a = find(a); b = find(b); if (a == b) return false; sz[a] += sz[b]; for (int i = 0; i < n; ++i) { int par = find(i); mat[i][a] += mat[i][b]; mat[a][i] += mat[b][i]; } p[b] = a; return true; } void initialize(int n) { ::n = n; for (int i = 0; i < n; ++i) { sz[i] = 1; p[i] = i; } } int hasEdge(int u, int v) { int U = find(u), V = find(v); if (U == V) return 0; ++mat[U][V]; ++mat[V][U]; if (sz[U] * sz[V] == mat[U][V]) { dsu(U, V); return 1; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 288 KB | Output is correct |
3 | Correct | 1 ms | 288 KB | Output is correct |
4 | Correct | 0 ms | 280 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 284 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 288 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 292 KB | Output is correct |
16 | Correct | 0 ms | 292 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 1 ms | 292 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 0 ms | 284 KB | Output is correct |
21 | Correct | 0 ms | 204 KB | Output is correct |
22 | Correct | 0 ms | 204 KB | Output is correct |
23 | Correct | 0 ms | 204 KB | Output is correct |
24 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 288 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 288 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 0 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 256 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 1 ms | 288 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 1 ms | 276 KB | Output is correct |
21 | Correct | 0 ms | 204 KB | Output is correct |
22 | Correct | 1 ms | 204 KB | Output is correct |
23 | Correct | 0 ms | 204 KB | Output is correct |
24 | Correct | 0 ms | 204 KB | Output is correct |
25 | Correct | 1 ms | 332 KB | Output is correct |
26 | Correct | 1 ms | 332 KB | Output is correct |
27 | Correct | 1 ms | 332 KB | Output is correct |
28 | Correct | 1 ms | 332 KB | Output is correct |
29 | Correct | 1 ms | 332 KB | Output is correct |
30 | Correct | 1 ms | 332 KB | Output is correct |
31 | Correct | 1 ms | 332 KB | Output is correct |
32 | Correct | 1 ms | 332 KB | Output is correct |
33 | Correct | 1 ms | 332 KB | Output is correct |
34 | Correct | 1 ms | 588 KB | Output is correct |
35 | Correct | 1 ms | 684 KB | Output is correct |
36 | Correct | 1 ms | 588 KB | Output is correct |
37 | Correct | 1 ms | 688 KB | Output is correct |
38 | Correct | 2 ms | 588 KB | Output is correct |
39 | Correct | 1 ms | 588 KB | Output is correct |
40 | Correct | 1 ms | 588 KB | Output is correct |
41 | Correct | 2 ms | 588 KB | Output is correct |
42 | Correct | 1 ms | 556 KB | Output is correct |
43 | Correct | 1 ms | 588 KB | Output is correct |
44 | Correct | 1 ms | 588 KB | Output is correct |
45 | Correct | 2 ms | 588 KB | Output is correct |
46 | Correct | 1 ms | 680 KB | Output is correct |
47 | Correct | 2 ms | 588 KB | Output is correct |
48 | Correct | 1 ms | 680 KB | Output is correct |
49 | Correct | 1 ms | 588 KB | Output is correct |
50 | Correct | 2 ms | 588 KB | Output is correct |
51 | Correct | 1 ms | 664 KB | Output is correct |
52 | Correct | 1 ms | 676 KB | Output is correct |
53 | Correct | 2 ms | 588 KB | Output is correct |
54 | Correct | 1 ms | 592 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 208 KB | Output is correct |
2 | Correct | 0 ms | 208 KB | Output is correct |
3 | Correct | 0 ms | 208 KB | Output is correct |
4 | Correct | 1 ms | 288 KB | Output is correct |
5 | Correct | 1 ms | 208 KB | Output is correct |
6 | Correct | 1 ms | 208 KB | Output is correct |
7 | Correct | 1 ms | 208 KB | Output is correct |
8 | Correct | 1 ms | 208 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 216 KB | Output is correct |
16 | Correct | 1 ms | 216 KB | Output is correct |
17 | Correct | 0 ms | 216 KB | Output is correct |
18 | Correct | 0 ms | 216 KB | Output is correct |
19 | Correct | 1 ms | 216 KB | Output is correct |
20 | Correct | 0 ms | 216 KB | Output is correct |
21 | Correct | 1 ms | 216 KB | Output is correct |
22 | Correct | 1 ms | 296 KB | Output is correct |
23 | Correct | 0 ms | 216 KB | Output is correct |
24 | Correct | 0 ms | 216 KB | Output is correct |
25 | Correct | 1 ms | 416 KB | Output is correct |
26 | Correct | 1 ms | 420 KB | Output is correct |
27 | Correct | 1 ms | 436 KB | Output is correct |
28 | Correct | 1 ms | 332 KB | Output is correct |
29 | Correct | 1 ms | 420 KB | Output is correct |
30 | Correct | 1 ms | 428 KB | Output is correct |
31 | Correct | 1 ms | 332 KB | Output is correct |
32 | Correct | 1 ms | 332 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 596 KB | Output is correct |
35 | Correct | 2 ms | 688 KB | Output is correct |
36 | Correct | 1 ms | 596 KB | Output is correct |
37 | Correct | 2 ms | 552 KB | Output is correct |
38 | Correct | 2 ms | 688 KB | Output is correct |
39 | Correct | 2 ms | 592 KB | Output is correct |
40 | Correct | 2 ms | 588 KB | Output is correct |
41 | Correct | 1 ms | 592 KB | Output is correct |
42 | Correct | 2 ms | 600 KB | Output is correct |
43 | Correct | 2 ms | 600 KB | Output is correct |
44 | Correct | 2 ms | 600 KB | Output is correct |
45 | Correct | 3 ms | 588 KB | Output is correct |
46 | Correct | 1 ms | 588 KB | Output is correct |
47 | Correct | 2 ms | 668 KB | Output is correct |
48 | Correct | 2 ms | 684 KB | Output is correct |
49 | Correct | 1 ms | 588 KB | Output is correct |
50 | Correct | 2 ms | 684 KB | Output is correct |
51 | Correct | 1 ms | 668 KB | Output is correct |
52 | Correct | 1 ms | 668 KB | Output is correct |
53 | Correct | 1 ms | 588 KB | Output is correct |
54 | Correct | 2 ms | 588 KB | Output is correct |
55 | Correct | 42 ms | 4940 KB | Output is correct |
56 | Correct | 42 ms | 5016 KB | Output is correct |
57 | Correct | 33 ms | 5016 KB | Output is correct |
58 | Correct | 37 ms | 4988 KB | Output is correct |
59 | Correct | 42 ms | 5008 KB | Output is correct |
60 | Correct | 35 ms | 5060 KB | Output is correct |
61 | Correct | 35 ms | 4972 KB | Output is correct |
62 | Correct | 43 ms | 5012 KB | Output is correct |
63 | Correct | 34 ms | 5020 KB | Output is correct |
64 | Correct | 32 ms | 4980 KB | Output is correct |
65 | Correct | 31 ms | 5040 KB | Output is correct |
66 | Correct | 38 ms | 5060 KB | Output is correct |
67 | Correct | 37 ms | 4992 KB | Output is correct |
68 | Correct | 34 ms | 4960 KB | Output is correct |
69 | Correct | 35 ms | 5012 KB | Output is correct |
70 | Correct | 34 ms | 5028 KB | Output is correct |
71 | Correct | 35 ms | 5052 KB | Output is correct |
72 | Correct | 54 ms | 4996 KB | Output is correct |
73 | Correct | 35 ms | 5060 KB | Output is correct |
74 | Correct | 38 ms | 4992 KB | Output is correct |
75 | Correct | 31 ms | 5024 KB | Output is correct |
76 | Correct | 85 ms | 8908 KB | Output is correct |
77 | Correct | 76 ms | 8860 KB | Output is correct |
78 | Correct | 76 ms | 8904 KB | Output is correct |
79 | Correct | 92 ms | 8832 KB | Output is correct |
80 | Correct | 82 ms | 8892 KB | Output is correct |
81 | Correct | 77 ms | 8932 KB | Output is correct |
82 | Correct | 86 ms | 8820 KB | Output is correct |
83 | Correct | 97 ms | 8880 KB | Output is correct |
84 | Correct | 77 ms | 8900 KB | Output is correct |
85 | Correct | 152 ms | 13348 KB | Output is correct |
86 | Correct | 149 ms | 13312 KB | Output is correct |
87 | Correct | 145 ms | 13376 KB | Output is correct |
88 | Correct | 158 ms | 13356 KB | Output is correct |
89 | Correct | 164 ms | 13344 KB | Output is correct |
90 | Correct | 157 ms | 13312 KB | Output is correct |
91 | Correct | 143 ms | 13332 KB | Output is correct |
92 | Correct | 147 ms | 13392 KB | Output is correct |
93 | Correct | 158 ms | 13356 KB | Output is correct |
94 | Correct | 347 ms | 25072 KB | Output is correct |
95 | Correct | 364 ms | 25024 KB | Output is correct |
96 | Correct | 389 ms | 25024 KB | Output is correct |
97 | Correct | 350 ms | 25060 KB | Output is correct |
98 | Correct | 345 ms | 24996 KB | Output is correct |
99 | Correct | 348 ms | 25104 KB | Output is correct |
100 | Correct | 408 ms | 25084 KB | Output is correct |