#include "bulb.h"
using namespace std;
int N, dlr[303030][2], dcn, par[303030], sw[303030], qsc, cha, ch[2], valid=-1, lose[303030];
vector<int> L, R;
int lca(int a, int b){
if(a==-1) return b;
if(a==-2) return a;
while(a>=0){
if(dlr[a][0] <= dlr[b][0] && dlr[b][0] <= dlr[a][1]) break;
a=par[a];
}
return a;
}
void pre(int ix){
if(ix<0) return;
dlr[ix][0]=dcn++;
pre(L[ix]), pre(R[ix]);
dlr[ix][1]=dcn-1;
}
void dfs(int pv, int ix){
if(ix==-1) return;
if(ix==-2){
if(cha==0) valid=-2;
if(cha==1 && qsc) valid=lca(valid,pv), lose[ch[0]]=1;
if(cha==2) lose[ch[0]]=lose[ch[1]]=1;
return;
}
par[ix]=pv;
sw[ix]=0, qsc--;
dfs(ix, L[ix]);
if(cha<2) ch[cha]=ix;
sw[ix]=1, cha++;
dfs(ix, R[ix]);
sw[ix]=2, cha--, qsc++;
}
int FindWinner(int T, vector<int> L_, vector<int> R_){
N=L_.size(), L=L_, R=R_;
for(int i=0; i<N; i++) sw[i]=2; qsc=N;
pre(0);
dfs(-1, 0);
if(valid==-2) return 0;
if(valid==-1){
for(int i=0; i<N; i++){
if(!lose[i]) return 1;
}
return 0;
}
for(int i=valid; i>=0; i=par[i]){
if(!lose[i]) return 1;
}
return 0;
}
Compilation message
bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:43:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0; i<N; i++) sw[i]=2; qsc=N;
^~~
bulb.cpp:43:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=0; i<N; i++) sw[i]=2; qsc=N;
^~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 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 |
380 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 |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 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 |
380 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 |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
114 ms |
15008 KB |
Output is correct |
| 28 |
Correct |
109 ms |
15220 KB |
Output is correct |
| 29 |
Correct |
107 ms |
14972 KB |
Output is correct |
| 30 |
Correct |
133 ms |
25508 KB |
Output is correct |
| 31 |
Correct |
133 ms |
25444 KB |
Output is correct |
| 32 |
Correct |
112 ms |
15040 KB |
Output is correct |
| 33 |
Correct |
105 ms |
15056 KB |
Output is correct |
| 34 |
Correct |
110 ms |
15096 KB |
Output is correct |
| 35 |
Correct |
109 ms |
15064 KB |
Output is correct |
| 36 |
Correct |
106 ms |
15036 KB |
Output is correct |
| 37 |
Correct |
105 ms |
14976 KB |
Output is correct |
| 38 |
Correct |
107 ms |
14992 KB |
Output is correct |
| 39 |
Correct |
105 ms |
15064 KB |
Output is correct |
| 40 |
Correct |
114 ms |
14996 KB |
Output is correct |
| 41 |
Correct |
107 ms |
14968 KB |
Output is correct |
| 42 |
Correct |
106 ms |
14984 KB |
Output is correct |
| 43 |
Correct |
105 ms |
14968 KB |
Output is correct |
| 44 |
Correct |
106 ms |
14920 KB |
Output is correct |
| 45 |
Correct |
106 ms |
14980 KB |
Output is correct |
| 46 |
Correct |
104 ms |
14968 KB |
Output is correct |
| 47 |
Correct |
115 ms |
18180 KB |
Output is correct |
| 48 |
Correct |
114 ms |
18312 KB |
Output is correct |
| 49 |
Correct |
111 ms |
18168 KB |
Output is correct |
| 50 |
Correct |
111 ms |
18104 KB |
Output is correct |
