#include <beechtree.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5+100;
int sz[N], dep[N], par[N], n;
vector<array<int, 2>> g[N], s[N];
vector<int> ans, COL;
set<int> C[N];
void dfs(int v){
ans[v] = 1;
sz[v] = 1;
s[v].pb({v, COL[v]});
for(auto U: g[v]){
int u = U[0], c = U[1];
dep[u] = dep[v] + 1;
par[u] = v;
dfs(u);
for(auto x: s[u]) s[v].pb(x);
sz[v] += sz[u];
ans[v] &= ans[u];
if(C[v].find(c) != C[v].end()) ans[v] = 0;
C[v].insert(c);
}
if(n <= 8){
sort(s[v].begin() + 1, s[v].end());
ans[v] = 0;
do{
bool ok = 1;
map<int, int> colptr;
for(int i = 1; i < s[v].size(); ++i){
int u = s[v][i][0], co = s[v][i][1];
if(par[u] != s[v][colptr[co]][0]){
ok = 0;
break;
}
colptr[co]++;
}
if(ok){
ans[v] = 1;
break;
}
}while(next_permutation(s[v].begin() + 1, s[v].end()));
}
else{
if(ans[v] == 0) return;
// sort(all(g[v]), [&](const array<int, 2> &x, const array<int, 2> &y){
// return sz[x[0]] > sz[y[0]];
// });
// for(int i = 0; i < g[v].size(); ++i){
// int x = (i == 0 ? v : g[v][i - 1][0]), y = g[v][i][0];
// for(auto col: C[y]){
// if(C[x].find(col) == C[x].end()){
// ans[v] = 0;
// break;
// }
// }
// }
// if(ans[v] == 0) return;
sort(all(s[v]), [&](const array<int, 2> &x, const array<int, 2> &y){
return (dep[x[0]] == dep[y[0]] ? COL[x[0]] < COL[y[0]]: dep[x[0]] < dep[y[0]]);
});
map<int, int> colptr;
for(int i = 1; i < s[v].size(); ++i){
int u = s[v][i][0], c = s[v][i][1];
if(par[u] != s[v][colptr[c]][0]){
ans[v] = 0;
return;
}
colptr[c]++;
}
}
}
vector<int> beechtree(int nn, int m, vector<int> P, vector<int> CC){
COL = CC;
n = nn;
for(int i = 1; i < n; ++i){
g[P[i]].pb({i, COL[i]});
}
ans.resize(n);
dep[0] = 0;
dfs(0);
return ans;
}
Compilation message
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 1; i < s[v].size(); ++i){
| ~~^~~~~~~~~~~~~
beechtree.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 1; i < s[v].size(); ++i){
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21104 KB |
Output is correct |
3 |
Correct |
5 ms |
21080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21080 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
5 ms |
21084 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
4 ms |
21084 KB |
Output is correct |
12 |
Correct |
4 ms |
21084 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21112 KB |
Output is correct |
15 |
Correct |
5 ms |
21084 KB |
Output is correct |
16 |
Correct |
5 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21084 KB |
Output is correct |
18 |
Correct |
4 ms |
21080 KB |
Output is correct |
19 |
Correct |
4 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21084 KB |
Output is correct |
21 |
Correct |
4 ms |
21084 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21080 KB |
Output is correct |
25 |
Correct |
4 ms |
21084 KB |
Output is correct |
26 |
Correct |
4 ms |
21084 KB |
Output is correct |
27 |
Correct |
4 ms |
21084 KB |
Output is correct |
28 |
Correct |
4 ms |
21080 KB |
Output is correct |
29 |
Correct |
5 ms |
21084 KB |
Output is correct |
30 |
Correct |
5 ms |
21284 KB |
Output is correct |
31 |
Correct |
5 ms |
21084 KB |
Output is correct |
32 |
Correct |
4 ms |
21084 KB |
Output is correct |
33 |
Correct |
5 ms |
20912 KB |
Output is correct |
34 |
Correct |
4 ms |
21084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21080 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Runtime error |
1388 ms |
2097152 KB |
Execution killed with signal 9 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21100 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21084 KB |
Output is correct |
8 |
Correct |
5 ms |
21084 KB |
Output is correct |
9 |
Incorrect |
4 ms |
21088 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Runtime error |
1388 ms |
2097152 KB |
Execution killed with signal 9 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21104 KB |
Output is correct |
3 |
Correct |
5 ms |
21080 KB |
Output is correct |
4 |
Correct |
4 ms |
21080 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21080 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
4 ms |
21084 KB |
Output is correct |
12 |
Correct |
4 ms |
21084 KB |
Output is correct |
13 |
Correct |
5 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21084 KB |
Output is correct |
15 |
Correct |
4 ms |
21084 KB |
Output is correct |
16 |
Correct |
4 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21112 KB |
Output is correct |
18 |
Correct |
5 ms |
21084 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21084 KB |
Output is correct |
21 |
Correct |
4 ms |
21080 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
4 ms |
21084 KB |
Output is correct |
26 |
Correct |
4 ms |
21084 KB |
Output is correct |
27 |
Correct |
4 ms |
21080 KB |
Output is correct |
28 |
Correct |
4 ms |
21084 KB |
Output is correct |
29 |
Correct |
4 ms |
21084 KB |
Output is correct |
30 |
Correct |
4 ms |
21084 KB |
Output is correct |
31 |
Correct |
4 ms |
21080 KB |
Output is correct |
32 |
Correct |
5 ms |
21084 KB |
Output is correct |
33 |
Correct |
5 ms |
21284 KB |
Output is correct |
34 |
Correct |
5 ms |
21084 KB |
Output is correct |
35 |
Correct |
4 ms |
21084 KB |
Output is correct |
36 |
Correct |
5 ms |
20912 KB |
Output is correct |
37 |
Correct |
4 ms |
21084 KB |
Output is correct |
38 |
Correct |
4 ms |
21080 KB |
Output is correct |
39 |
Correct |
4 ms |
21084 KB |
Output is correct |
40 |
Correct |
4 ms |
21084 KB |
Output is correct |
41 |
Correct |
4 ms |
21084 KB |
Output is correct |
42 |
Correct |
4 ms |
21100 KB |
Output is correct |
43 |
Correct |
4 ms |
21084 KB |
Output is correct |
44 |
Correct |
4 ms |
21084 KB |
Output is correct |
45 |
Correct |
5 ms |
21084 KB |
Output is correct |
46 |
Incorrect |
4 ms |
21088 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
47 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
5 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21084 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
4 ms |
21112 KB |
Output is correct |
11 |
Correct |
5 ms |
21084 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21080 KB |
Output is correct |
15 |
Correct |
4 ms |
21084 KB |
Output is correct |
16 |
Correct |
4 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21084 KB |
Output is correct |
18 |
Correct |
4 ms |
21084 KB |
Output is correct |
19 |
Correct |
4 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21080 KB |
Output is correct |
21 |
Correct |
4 ms |
21084 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21080 KB |
Output is correct |
25 |
Correct |
51 ms |
41812 KB |
Output is correct |
26 |
Correct |
33 ms |
41820 KB |
Output is correct |
27 |
Correct |
24 ms |
41808 KB |
Output is correct |
28 |
Correct |
16 ms |
41820 KB |
Output is correct |
29 |
Correct |
48 ms |
41888 KB |
Output is correct |
30 |
Incorrect |
8 ms |
23388 KB |
2nd lines differ - on the 6th token, expected: '1', found: '0' |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21104 KB |
Output is correct |
3 |
Correct |
5 ms |
21080 KB |
Output is correct |
4 |
Correct |
4 ms |
21080 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21080 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
4 ms |
21084 KB |
Output is correct |
12 |
Correct |
4 ms |
21084 KB |
Output is correct |
13 |
Correct |
5 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21084 KB |
Output is correct |
15 |
Correct |
4 ms |
21084 KB |
Output is correct |
16 |
Correct |
4 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21112 KB |
Output is correct |
18 |
Correct |
5 ms |
21084 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21084 KB |
Output is correct |
21 |
Correct |
4 ms |
21080 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
4 ms |
21084 KB |
Output is correct |
26 |
Correct |
4 ms |
21084 KB |
Output is correct |
27 |
Correct |
4 ms |
21080 KB |
Output is correct |
28 |
Correct |
4 ms |
21084 KB |
Output is correct |
29 |
Correct |
4 ms |
21084 KB |
Output is correct |
30 |
Correct |
4 ms |
21084 KB |
Output is correct |
31 |
Correct |
4 ms |
21080 KB |
Output is correct |
32 |
Correct |
5 ms |
21084 KB |
Output is correct |
33 |
Correct |
5 ms |
21284 KB |
Output is correct |
34 |
Correct |
5 ms |
21084 KB |
Output is correct |
35 |
Correct |
4 ms |
21084 KB |
Output is correct |
36 |
Correct |
5 ms |
20912 KB |
Output is correct |
37 |
Correct |
4 ms |
21084 KB |
Output is correct |
38 |
Correct |
4 ms |
21080 KB |
Output is correct |
39 |
Correct |
4 ms |
21084 KB |
Output is correct |
40 |
Correct |
4 ms |
21084 KB |
Output is correct |
41 |
Correct |
4 ms |
21084 KB |
Output is correct |
42 |
Correct |
4 ms |
21100 KB |
Output is correct |
43 |
Correct |
4 ms |
21084 KB |
Output is correct |
44 |
Correct |
4 ms |
21084 KB |
Output is correct |
45 |
Correct |
5 ms |
21084 KB |
Output is correct |
46 |
Incorrect |
4 ms |
21088 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
47 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
4 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
5 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21084 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
4 ms |
21112 KB |
Output is correct |
11 |
Correct |
5 ms |
21084 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21080 KB |
Output is correct |
15 |
Correct |
4 ms |
21084 KB |
Output is correct |
16 |
Correct |
4 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21084 KB |
Output is correct |
18 |
Correct |
4 ms |
21084 KB |
Output is correct |
19 |
Correct |
4 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21080 KB |
Output is correct |
21 |
Correct |
4 ms |
21084 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21080 KB |
Output is correct |
25 |
Correct |
51 ms |
41812 KB |
Output is correct |
26 |
Correct |
33 ms |
41820 KB |
Output is correct |
27 |
Correct |
24 ms |
41808 KB |
Output is correct |
28 |
Correct |
16 ms |
41820 KB |
Output is correct |
29 |
Correct |
48 ms |
41888 KB |
Output is correct |
30 |
Incorrect |
8 ms |
23388 KB |
2nd lines differ - on the 6th token, expected: '1', found: '0' |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21104 KB |
Output is correct |
3 |
Correct |
5 ms |
21080 KB |
Output is correct |
4 |
Correct |
4 ms |
21080 KB |
Output is correct |
5 |
Correct |
4 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21080 KB |
Output is correct |
8 |
Correct |
4 ms |
21084 KB |
Output is correct |
9 |
Correct |
4 ms |
21084 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
4 ms |
21084 KB |
Output is correct |
12 |
Correct |
4 ms |
21084 KB |
Output is correct |
13 |
Correct |
5 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
21084 KB |
Output is correct |
15 |
Correct |
4 ms |
21084 KB |
Output is correct |
16 |
Correct |
4 ms |
21084 KB |
Output is correct |
17 |
Correct |
4 ms |
21112 KB |
Output is correct |
18 |
Correct |
5 ms |
21084 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
4 ms |
21084 KB |
Output is correct |
21 |
Correct |
4 ms |
21080 KB |
Output is correct |
22 |
Correct |
4 ms |
21084 KB |
Output is correct |
23 |
Correct |
4 ms |
21084 KB |
Output is correct |
24 |
Correct |
4 ms |
21084 KB |
Output is correct |
25 |
Correct |
4 ms |
21084 KB |
Output is correct |
26 |
Correct |
4 ms |
21084 KB |
Output is correct |
27 |
Correct |
4 ms |
21080 KB |
Output is correct |
28 |
Correct |
4 ms |
21084 KB |
Output is correct |
29 |
Correct |
4 ms |
21084 KB |
Output is correct |
30 |
Correct |
4 ms |
21084 KB |
Output is correct |
31 |
Correct |
4 ms |
21080 KB |
Output is correct |
32 |
Correct |
5 ms |
21084 KB |
Output is correct |
33 |
Correct |
5 ms |
21284 KB |
Output is correct |
34 |
Correct |
5 ms |
21084 KB |
Output is correct |
35 |
Correct |
4 ms |
21084 KB |
Output is correct |
36 |
Correct |
5 ms |
20912 KB |
Output is correct |
37 |
Correct |
4 ms |
21084 KB |
Output is correct |
38 |
Runtime error |
1388 ms |
2097152 KB |
Execution killed with signal 9 |
39 |
Halted |
0 ms |
0 KB |
- |