#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>> child;
vector<int> C;
vector<int> P;
vector<int> outp;
std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
N=n; M=m;
C.assign(c.begin(), c.end());
P.assign(p.begin(), p.end());
child.resize(n);
outp.resize(n,0);
P[0]=0;
vector<int> depth(N,0);
vector<bool> triple(N,false);
for (int i = 1; i < N; i++) child[P[i]].push_back(i);
for (int i = 1; i < N; i++) {
if(P[P[P[i]]]!=P[P[i]]) triple[P[P[P[i]]]]=true;
}
for (int i = 0; i < n; i++)
{
if(child[i].size()>2||triple[i]) continue;
else if(child[i].size()==0) outp[i]=1;
else if(child[i].size()==2) {
unordered_set<int> childColor;
for (auto u : child[i]) childColor.insert(c[u]);
unordered_set<int> child1Color;
unordered_set<int> child2Color;
if(triple[i]||childColor.size()!=2||(child[child[i][0]].size()+child[child[i][1]].size())>2) continue;
for (auto u : child[child[i][0]])
{
child1Color.insert(c[u]);
childColor.insert(c[u]);
}
if(child1Color.size()!=child[child[i][0]].size()) continue;
for (auto u : child[child[i][1]])
{
child1Color.insert(c[u]);
child2Color.insert(c[u]);
childColor.insert(c[u]);
}
if(child2Color.size()!=child[child[i][1]].size()) continue;
if(child1Color.size()!=child[child[i][0]].size()+child[child[i][1]].size()) continue;
if(childColor.size()!=2) continue;
outp[i]=1;
}else{
if(triple[i]) continue;
outp[i]=1;
int u=i;
int l=c[u];
while(child[u].size()>0){
if(child[u].size()!=1||l!=c[u]) { outp[i]=0; break; }
u=child[u][0];
l=c[u];
}
if(child[u].size()!=1||l!=c[u]) outp[i]=0;
}
}
return {outp};
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 |
Halted |
0 ms |
0 KB |
- |