# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
133336 | 2019-07-20T12:17:14 Z | sealnot123 | Game (IOI14_game) | C++14 | 689 ms | 22916 KB |
#include "game.h" #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 1505; int n, sq; int sqg[N][N], g[N][N], l[N], r[N]; int mk[N]; queue<int> bfs; bool check(int a){ int b = a*sq; int i, j = 1; for(i = l[b]; i < r[b]; i++){ mk[i] = 0; } mk[b] = 1; bfs.push(b); while(!bfs.empty()){ int u = bfs.front(); bfs.pop(); for(i = l[u]; i < r[u]; i++){ if(!g[u][i] || mk[i]) continue; j++; mk[i] = 1; bfs.push(i); } } return j == r[b]-l[b]; } bool check_group(){ int a = (n+sq-1)/sq; int i, j = 1; for(i = 0; i < a; i++){ mk[i] = 0; } mk[0] = 1; bfs.push(0); while(!bfs.empty()){ int u = bfs.front(); bfs.pop(); for(i = 0; i < a; i++){ if(!sqg[u][i] || mk[i]) continue; mk[i] = 1; j++; bfs.push(i); } } return j == a; } void initialize(int nn) { n = nn; LL i, j, a, b, c; sq = sqrt(nn); for(i = 0; i < n; i++){ for(j = i+1; j < n; j++){ a = i/sq; b = j/sq; if(a == b) g[i][j] = g[j][i] = 1; else sqg[a][b]++,sqg[b][a]++; } l[i] = i/sq*sq; r[i] = min(i/sq*sq+sq, (LL)n); } } int hasEdge(int u, int v) { if(u > v) swap(u, v); int i, j, a, b, res; a = u/sq; b = v/sq; if(a == b){ g[u][v] = g[v][u] = 0; res = check(a); if(!res){ g[u][v] = g[v][u] = 1; return 1; } return 0; }else{ sqg[a][b]--; sqg[b][a]--; if(sqg[a][b] != 0) return 0; res = check_group(); if(!res){ sqg[a][b]++; sqg[b][a]++; return 1; } return 0; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 376 KB | Output is correct |
23 | Correct | 2 ms | 376 KB | Output is correct |
24 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 296 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 376 KB | Output is correct |
23 | Correct | 2 ms | 376 KB | Output is correct |
24 | Correct | 2 ms | 376 KB | Output is correct |
25 | Correct | 2 ms | 504 KB | Output is correct |
26 | Correct | 2 ms | 504 KB | Output is correct |
27 | Correct | 2 ms | 504 KB | Output is correct |
28 | Correct | 2 ms | 504 KB | Output is correct |
29 | Correct | 2 ms | 508 KB | Output is correct |
30 | Correct | 2 ms | 504 KB | Output is correct |
31 | Correct | 2 ms | 504 KB | Output is correct |
32 | Correct | 2 ms | 504 KB | Output is correct |
33 | Correct | 2 ms | 504 KB | Output is correct |
34 | Correct | 3 ms | 760 KB | Output is correct |
35 | Correct | 4 ms | 760 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 3 ms | 760 KB | Output is correct |
38 | Correct | 4 ms | 760 KB | Output is correct |
39 | Correct | 4 ms | 760 KB | Output is correct |
40 | Correct | 4 ms | 760 KB | Output is correct |
41 | Correct | 4 ms | 760 KB | Output is correct |
42 | Correct | 3 ms | 760 KB | Output is correct |
43 | Correct | 3 ms | 888 KB | Output is correct |
44 | Correct | 3 ms | 760 KB | Output is correct |
45 | Correct | 3 ms | 760 KB | Output is correct |
46 | Correct | 3 ms | 760 KB | Output is correct |
47 | Correct | 4 ms | 760 KB | Output is correct |
48 | Correct | 4 ms | 760 KB | Output is correct |
49 | Correct | 4 ms | 760 KB | Output is correct |
50 | Correct | 4 ms | 760 KB | Output is correct |
51 | Correct | 3 ms | 760 KB | Output is correct |
52 | Correct | 3 ms | 760 KB | Output is correct |
53 | Correct | 4 ms | 760 KB | Output is correct |
54 | Correct | 4 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 380 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 380 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 376 KB | Output is correct |
23 | Correct | 2 ms | 376 KB | Output is correct |
24 | Correct | 2 ms | 376 KB | Output is correct |
25 | Correct | 2 ms | 504 KB | Output is correct |
26 | Correct | 2 ms | 552 KB | Output is correct |
27 | Correct | 2 ms | 504 KB | Output is correct |
28 | Correct | 2 ms | 504 KB | Output is correct |
29 | Correct | 2 ms | 504 KB | Output is correct |
30 | Correct | 3 ms | 504 KB | Output is correct |
31 | Correct | 2 ms | 504 KB | Output is correct |
32 | Correct | 2 ms | 504 KB | Output is correct |
33 | Correct | 2 ms | 504 KB | Output is correct |
34 | Correct | 3 ms | 760 KB | Output is correct |
35 | Correct | 3 ms | 760 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 3 ms | 760 KB | Output is correct |
38 | Correct | 3 ms | 760 KB | Output is correct |
39 | Correct | 3 ms | 760 KB | Output is correct |
40 | Correct | 3 ms | 760 KB | Output is correct |
41 | Correct | 4 ms | 760 KB | Output is correct |
42 | Correct | 4 ms | 760 KB | Output is correct |
43 | Correct | 3 ms | 760 KB | Output is correct |
44 | Correct | 3 ms | 764 KB | Output is correct |
45 | Correct | 3 ms | 764 KB | Output is correct |
46 | Correct | 3 ms | 760 KB | Output is correct |
47 | Correct | 4 ms | 760 KB | Output is correct |
48 | Correct | 4 ms | 760 KB | Output is correct |
49 | Correct | 4 ms | 760 KB | Output is correct |
50 | Correct | 4 ms | 760 KB | Output is correct |
51 | Correct | 3 ms | 760 KB | Output is correct |
52 | Correct | 3 ms | 760 KB | Output is correct |
53 | Correct | 3 ms | 760 KB | Output is correct |
54 | Correct | 4 ms | 760 KB | Output is correct |
55 | Correct | 65 ms | 3576 KB | Output is correct |
56 | Correct | 65 ms | 3584 KB | Output is correct |
57 | Correct | 65 ms | 3576 KB | Output is correct |
58 | Correct | 69 ms | 3576 KB | Output is correct |
59 | Correct | 66 ms | 3576 KB | Output is correct |
60 | Correct | 65 ms | 3576 KB | Output is correct |
61 | Correct | 65 ms | 3580 KB | Output is correct |
62 | Correct | 65 ms | 3576 KB | Output is correct |
63 | Correct | 66 ms | 3596 KB | Output is correct |
64 | Correct | 56 ms | 3540 KB | Output is correct |
65 | Correct | 57 ms | 3576 KB | Output is correct |
66 | Correct | 65 ms | 3568 KB | Output is correct |
67 | Correct | 66 ms | 3576 KB | Output is correct |
68 | Correct | 66 ms | 3580 KB | Output is correct |
69 | Correct | 65 ms | 3468 KB | Output is correct |
70 | Correct | 67 ms | 3576 KB | Output is correct |
71 | Correct | 62 ms | 3576 KB | Output is correct |
72 | Correct | 62 ms | 3576 KB | Output is correct |
73 | Correct | 63 ms | 3576 KB | Output is correct |
74 | Correct | 64 ms | 3576 KB | Output is correct |
75 | Correct | 63 ms | 3496 KB | Output is correct |
76 | Correct | 156 ms | 5884 KB | Output is correct |
77 | Correct | 157 ms | 5880 KB | Output is correct |
78 | Correct | 157 ms | 5880 KB | Output is correct |
79 | Correct | 156 ms | 5916 KB | Output is correct |
80 | Correct | 157 ms | 5884 KB | Output is correct |
81 | Correct | 157 ms | 5880 KB | Output is correct |
82 | Correct | 158 ms | 5880 KB | Output is correct |
83 | Correct | 158 ms | 6020 KB | Output is correct |
84 | Correct | 160 ms | 5880 KB | Output is correct |
85 | Correct | 299 ms | 8280 KB | Output is correct |
86 | Correct | 300 ms | 8188 KB | Output is correct |
87 | Correct | 315 ms | 8184 KB | Output is correct |
88 | Correct | 305 ms | 8184 KB | Output is correct |
89 | Correct | 299 ms | 8184 KB | Output is correct |
90 | Correct | 299 ms | 8184 KB | Output is correct |
91 | Correct | 297 ms | 8236 KB | Output is correct |
92 | Correct | 309 ms | 8140 KB | Output is correct |
93 | Correct | 296 ms | 8184 KB | Output is correct |
94 | Correct | 681 ms | 14044 KB | Output is correct |
95 | Correct | 685 ms | 22776 KB | Output is correct |
96 | Correct | 684 ms | 22904 KB | Output is correct |
97 | Correct | 686 ms | 22776 KB | Output is correct |
98 | Correct | 689 ms | 22916 KB | Output is correct |
99 | Correct | 685 ms | 22904 KB | Output is correct |
100 | Correct | 689 ms | 22904 KB | Output is correct |