#include "bulb.h"
#include <vector>
using namespace std;
vector<int> L, R;
int n;
vector<int> ch[300001];
int dep[300001];
bool imp[300001];
int need[300001];
int all;
void dfs(int x) {
while (ch[x].size() > 3) ch[x].pop_back();
if (L[x] < 0) {
if (L[x] == -1);
else if (ch[x].size() > 2);
else if (ch[x].size() == 2) {
imp[ch[x][0]] = imp[ch[x][1]] = 1;
}
else if (ch[x].size() == 1) {
++need[x];
++all;
if (dep[x] < n - 1) imp[ch[x][0]] = 1;
}
else {
throw 0;
}
}
else {
dep[L[x]] = dep[x] + 1;
for (int i : ch[x]) ch[L[x]].push_back(i);
dfs(L[x]);
need[x] += need[L[x]];
}
ch[x].push_back(x);
if (R[x] < 0) {
if (R[x] == -1);
else if (ch[x].size() > 2);
else if (ch[x].size() == 2) {
imp[ch[x][0]] = imp[ch[x][1]] = 1;
}
else if (ch[x].size() == 1) {
++need[x];
++all;
if (dep[x] < n - 1) imp[ch[x][0]] = 1;
}
else {
throw 0;
}
}
else {
dep[R[x]] = dep[x] + 1;
for (int i : ch[x]) ch[R[x]].push_back(i);
dfs(R[x]);
need[x] += need[R[x]];
}
}
int FindWinner(int T, vector<int> _L, vector<int> _R) {
n = _L.size();
L = _L;
R = _R;
try {
dfs(0);
for (int i = 0; i < n; ++i) {
if (need[i] == all && !imp[i]) throw 1;
}
throw 0;
} catch (int ret) {
return ret;
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7544 KB |
Output is correct |
5 |
Correct |
9 ms |
7544 KB |
Output is correct |
6 |
Correct |
9 ms |
7416 KB |
Output is correct |
7 |
Correct |
9 ms |
7472 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7416 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
11 |
Correct |
9 ms |
7416 KB |
Output is correct |
12 |
Correct |
9 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
9 ms |
7544 KB |
Output is correct |
7 |
Correct |
9 ms |
7544 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7472 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
11 |
Correct |
9 ms |
7416 KB |
Output is correct |
12 |
Correct |
9 ms |
7416 KB |
Output is correct |
13 |
Correct |
9 ms |
7416 KB |
Output is correct |
14 |
Correct |
9 ms |
7416 KB |
Output is correct |
15 |
Correct |
9 ms |
7416 KB |
Output is correct |
16 |
Correct |
9 ms |
7416 KB |
Output is correct |
17 |
Correct |
9 ms |
7416 KB |
Output is correct |
18 |
Correct |
9 ms |
7532 KB |
Output is correct |
19 |
Correct |
10 ms |
7588 KB |
Output is correct |
20 |
Correct |
9 ms |
7416 KB |
Output is correct |
21 |
Correct |
9 ms |
7392 KB |
Output is correct |
22 |
Correct |
9 ms |
7468 KB |
Output is correct |
23 |
Correct |
9 ms |
7416 KB |
Output is correct |
24 |
Correct |
9 ms |
7388 KB |
Output is correct |
25 |
Correct |
9 ms |
7388 KB |
Output is correct |
26 |
Correct |
9 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
9 ms |
7544 KB |
Output is correct |
7 |
Correct |
9 ms |
7544 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7472 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
11 |
Correct |
9 ms |
7416 KB |
Output is correct |
12 |
Correct |
9 ms |
7416 KB |
Output is correct |
13 |
Correct |
9 ms |
7416 KB |
Output is correct |
14 |
Correct |
9 ms |
7416 KB |
Output is correct |
15 |
Correct |
9 ms |
7416 KB |
Output is correct |
16 |
Correct |
9 ms |
7416 KB |
Output is correct |
17 |
Correct |
9 ms |
7416 KB |
Output is correct |
18 |
Correct |
9 ms |
7532 KB |
Output is correct |
19 |
Correct |
10 ms |
7588 KB |
Output is correct |
20 |
Correct |
9 ms |
7416 KB |
Output is correct |
21 |
Correct |
9 ms |
7392 KB |
Output is correct |
22 |
Correct |
9 ms |
7468 KB |
Output is correct |
23 |
Correct |
9 ms |
7416 KB |
Output is correct |
24 |
Correct |
9 ms |
7388 KB |
Output is correct |
25 |
Correct |
9 ms |
7388 KB |
Output is correct |
26 |
Correct |
9 ms |
7516 KB |
Output is correct |
27 |
Correct |
78 ms |
14496 KB |
Output is correct |
28 |
Correct |
189 ms |
26304 KB |
Output is correct |
29 |
Correct |
186 ms |
26196 KB |
Output is correct |
30 |
Correct |
172 ms |
46352 KB |
Output is correct |
31 |
Correct |
177 ms |
46312 KB |
Output is correct |
32 |
Correct |
210 ms |
27048 KB |
Output is correct |
33 |
Correct |
197 ms |
27920 KB |
Output is correct |
34 |
Correct |
189 ms |
27944 KB |
Output is correct |
35 |
Correct |
189 ms |
27064 KB |
Output is correct |
36 |
Correct |
185 ms |
27920 KB |
Output is correct |
37 |
Correct |
182 ms |
27576 KB |
Output is correct |
38 |
Correct |
182 ms |
27876 KB |
Output is correct |
39 |
Correct |
178 ms |
27824 KB |
Output is correct |
40 |
Correct |
181 ms |
26836 KB |
Output is correct |
41 |
Correct |
189 ms |
26752 KB |
Output is correct |
42 |
Correct |
184 ms |
27852 KB |
Output is correct |
43 |
Correct |
186 ms |
27812 KB |
Output is correct |
44 |
Correct |
192 ms |
27776 KB |
Output is correct |
45 |
Correct |
186 ms |
27184 KB |
Output is correct |
46 |
Correct |
192 ms |
27916 KB |
Output is correct |
47 |
Correct |
191 ms |
31132 KB |
Output is correct |
48 |
Correct |
197 ms |
32040 KB |
Output is correct |
49 |
Correct |
185 ms |
32296 KB |
Output is correct |
50 |
Correct |
185 ms |
30632 KB |
Output is correct |