| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576014 |
2022-06-12T04:47:42 Z |
WongChun1234 |
Game (APIO22_game) |
C++17 |
|
1632 ms |
55908 KB |
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int N=300050;
int n,k,l[N],r[N];
vector<int> adj[N],radj[N];
void init(int nn, int kk) {
n=nn; k=kk;
for (int i=0;i<=k;i++) l[i]=i,r[i]=i+1;
for (int i=k+1;i<=n;i++) l[i]=0,r[i]=k+1;
for (int i=0;i<=n;i++) adj[i].clear(),radj[i].clear();
}
bool addedge(int u,int v){
//cerr<<u<<":"<<l[u]<<"-"<<r[u]<<"->"<<v<<":"<<l[v]<<"-"<<r[v]<<"\n";
if (r[u]<=l[v]) return 0;
if (l[u]>=r[v]) return 1;
if (l[u]==l[v]&&r[u]==r[v]) return 0;
if (r[v]<=(l[u]+r[u])/2){
r[u]=(l[u]+r[u])/2;
for (int i:radj[u]) if (addedge(i,u)) return 1;
for (int i:adj[u]) if (addedge(u,i)) return 1;
}else if (l[u]>=(l[v]+r[v])/2){
l[v]=(l[v]+r[v])/2;
for (int i:adj[v]) if (addedge(v,i)) return 1;
for (int i:radj[v]) if (addedge(i,v)) return 1;
}
return 0;
}
int add_teleporter(int u, int v) {
u++;
if (v>=k) v++;
adj[u].push_back(v);
radj[v].push_back(u);
return addedge(u,v);
}
/*
6 5 3
3 4
5 0
4 5
5 3
1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14340 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14524 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14340 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14524 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14360 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14404 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14340 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14524 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14360 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14404 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14396 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14436 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14308 KB |
Output is correct |
| 22 |
Correct |
9 ms |
14348 KB |
Output is correct |
| 23 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 24 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 25 |
Correct |
11 ms |
14416 KB |
Output is correct |
| 26 |
Correct |
12 ms |
14452 KB |
Output is correct |
| 27 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 28 |
Correct |
11 ms |
14544 KB |
Output is correct |
| 29 |
Correct |
10 ms |
14544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14340 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14524 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14360 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14404 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14396 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14436 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14308 KB |
Output is correct |
| 22 |
Correct |
9 ms |
14348 KB |
Output is correct |
| 23 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 24 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 25 |
Correct |
11 ms |
14416 KB |
Output is correct |
| 26 |
Correct |
12 ms |
14452 KB |
Output is correct |
| 27 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 28 |
Correct |
11 ms |
14544 KB |
Output is correct |
| 29 |
Correct |
10 ms |
14544 KB |
Output is correct |
| 30 |
Correct |
26 ms |
15728 KB |
Output is correct |
| 31 |
Correct |
11 ms |
14928 KB |
Output is correct |
| 32 |
Correct |
36 ms |
17748 KB |
Output is correct |
| 33 |
Correct |
34 ms |
16384 KB |
Output is correct |
| 34 |
Correct |
48 ms |
19088 KB |
Output is correct |
| 35 |
Correct |
46 ms |
17424 KB |
Output is correct |
| 36 |
Correct |
51 ms |
16508 KB |
Output is correct |
| 37 |
Correct |
50 ms |
16420 KB |
Output is correct |
| 38 |
Correct |
53 ms |
16136 KB |
Output is correct |
| 39 |
Correct |
47 ms |
16272 KB |
Output is correct |
| 40 |
Correct |
46 ms |
18988 KB |
Output is correct |
| 41 |
Correct |
38 ms |
17716 KB |
Output is correct |
| 42 |
Correct |
41 ms |
16620 KB |
Output is correct |
| 43 |
Correct |
54 ms |
17296 KB |
Output is correct |
| 44 |
Correct |
57 ms |
17452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14340 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14524 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14288 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14360 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14404 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14288 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14288 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14396 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14436 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14308 KB |
Output is correct |
| 22 |
Correct |
9 ms |
14348 KB |
Output is correct |
| 23 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 24 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 25 |
Correct |
11 ms |
14416 KB |
Output is correct |
| 26 |
Correct |
12 ms |
14452 KB |
Output is correct |
| 27 |
Correct |
10 ms |
14416 KB |
Output is correct |
| 28 |
Correct |
11 ms |
14544 KB |
Output is correct |
| 29 |
Correct |
10 ms |
14544 KB |
Output is correct |
| 30 |
Correct |
26 ms |
15728 KB |
Output is correct |
| 31 |
Correct |
11 ms |
14928 KB |
Output is correct |
| 32 |
Correct |
36 ms |
17748 KB |
Output is correct |
| 33 |
Correct |
34 ms |
16384 KB |
Output is correct |
| 34 |
Correct |
48 ms |
19088 KB |
Output is correct |
| 35 |
Correct |
46 ms |
17424 KB |
Output is correct |
| 36 |
Correct |
51 ms |
16508 KB |
Output is correct |
| 37 |
Correct |
50 ms |
16420 KB |
Output is correct |
| 38 |
Correct |
53 ms |
16136 KB |
Output is correct |
| 39 |
Correct |
47 ms |
16272 KB |
Output is correct |
| 40 |
Correct |
46 ms |
18988 KB |
Output is correct |
| 41 |
Correct |
38 ms |
17716 KB |
Output is correct |
| 42 |
Correct |
41 ms |
16620 KB |
Output is correct |
| 43 |
Correct |
54 ms |
17296 KB |
Output is correct |
| 44 |
Correct |
57 ms |
17452 KB |
Output is correct |
| 45 |
Correct |
301 ms |
28080 KB |
Output is correct |
| 46 |
Correct |
19 ms |
17116 KB |
Output is correct |
| 47 |
Correct |
14 ms |
17000 KB |
Output is correct |
| 48 |
Correct |
354 ms |
41528 KB |
Output is correct |
| 49 |
Correct |
305 ms |
35444 KB |
Output is correct |
| 50 |
Correct |
775 ms |
45504 KB |
Output is correct |
| 51 |
Correct |
1014 ms |
42008 KB |
Output is correct |
| 52 |
Correct |
692 ms |
35340 KB |
Output is correct |
| 53 |
Correct |
897 ms |
35568 KB |
Output is correct |
| 54 |
Correct |
1087 ms |
35212 KB |
Output is correct |
| 55 |
Correct |
1203 ms |
35964 KB |
Output is correct |
| 56 |
Correct |
1430 ms |
35660 KB |
Output is correct |
| 57 |
Correct |
498 ms |
29416 KB |
Output is correct |
| 58 |
Correct |
535 ms |
29584 KB |
Output is correct |
| 59 |
Correct |
539 ms |
29548 KB |
Output is correct |
| 60 |
Correct |
584 ms |
29548 KB |
Output is correct |
| 61 |
Correct |
757 ms |
29152 KB |
Output is correct |
| 62 |
Correct |
500 ms |
37096 KB |
Output is correct |
| 63 |
Correct |
456 ms |
33772 KB |
Output is correct |
| 64 |
Correct |
1181 ms |
55908 KB |
Output is correct |
| 65 |
Correct |
542 ms |
35004 KB |
Output is correct |
| 66 |
Correct |
454 ms |
30916 KB |
Output is correct |
| 67 |
Correct |
875 ms |
39948 KB |
Output is correct |
| 68 |
Correct |
202 ms |
26352 KB |
Output is correct |
| 69 |
Correct |
50 ms |
20140 KB |
Output is correct |
| 70 |
Correct |
883 ms |
38480 KB |
Output is correct |
| 71 |
Correct |
317 ms |
29140 KB |
Output is correct |
| 72 |
Correct |
240 ms |
24888 KB |
Output is correct |
| 73 |
Correct |
736 ms |
40588 KB |
Output is correct |
| 74 |
Correct |
1632 ms |
35184 KB |
Output is correct |
| 75 |
Correct |
1237 ms |
42876 KB |
Output is correct |
| 76 |
Correct |
1259 ms |
45988 KB |
Output is correct |
