#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
std::vector<signed> beechtree(signed N, signed M, std::vector<signed> P, std::vector<signed> C) {
int n=N; int m=M;
//if any vertex has 2 children with same color then it jambloats
//also any vertex must be before its child in ordering since if ind[parent]>ind[child] then there are
//ind[parent]-1 edges considered for child contradiction hyperbloat
//also consider in the order of a permutation, for each color, it starts being on and turns off at some point
//in the edges leading from a node to its children
//thus consider the vertices which have each color in children, and make an ordering
//if the ordering is consistent, hope it works
//insufficient
//increasing order of subtree size?
//add condition that if color of par[x]->x and color of par[y]->y are the same, put from the par with larger subtree into par with smaller subtree
//this also deals with the 2 children same color thing
vector<int> subsize(n,1);
vector<vector<int>> subtree(n);
vector<vector<int>> sons(n);
for (int i=0; i<n; i++) subtree[i] = {i};
for (int i=n-1; i>=1; i--) {
subsize[P[i]]+=subsize[i];
for (int j:subtree[i]) {
subtree[P[i]].push_back(j);
}
sons[P[i]].push_back(i);
}
vector<int> ans(n,1);
for (int root=0; root<n; root++) {
vector<int> relevant=subtree[root];
map<int,int> revcoords;
for (int j=0; j<relevant.size(); j++) {
revcoords[relevant[j]] = j;
}
/*vector<vector<int>> adjlist(relevant.size());
vector<vector<int>> sonsv2(relevant.size());
for (int i:relevant) {
for (int j:sons[i]) {
adjlist[revcoords[i]].push_back(revcoords[j]);
sonsv2[revcoords[i]].push_back(revcoords[j]);
}
}
for (int j=1; j<dep1.size(); j++) {
if (subsize[relevant[dep1[j-1]]]<subsize[relevant[dep1[j]]]) {
adjlist[dep1[j]].push_back(dep1[j-1]);
}
}
map<int,vector<int>> revcols;
for (int i:relevant) {
if (i!=root) {
revcols[C[i]].push_back(revcoords[i]);
}
}
for (auto i:revcols) {
vector<int> dep1 = i.second;
sort(dep1.begin(), dep1.end(), [&](const int i1, const int i2) {
return subsize[relevant[i1]]<subsize[relevant[i2]]
});
for (int j=1; j<dep1.size(); j++) {
if (subsize[relevant[dep1[j-1]]]<subsize[relevant[dep1[j]]]) {
adjlist[dep1[j]].push_back(dep1[j-1]);
}
}
}*/
vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
sort(dep1.begin(), dep1.end(), [&](const int i1, const int i2) {
return subsize[relevant[i1]]<subsize[relevant[i2]];
});
map<int,int> colors;
int fail = 0;
for (int i=0; i<dep1.size(); i++) {
int node = dep1[i];
for (int j:sons[relevant[node]]) {
if (i>0 && colors[C[j]]<subsize[j]) {
fail=1;
}
colors[C[j]] = subsize[j];
}
}
ans[root] = 1-fail;
}
vector<signed> ans2(ans.begin(), ans.end());
return ans2;
}
Compilation message
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:37:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int j=0; j<relevant.size(); j++) {
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:71:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i=0; i<dep1.size(); i++) {
| ~^~~~~~~~~~~~
beechtree.cpp:9:18: warning: unused variable 'm' [-Wunused-variable]
9 | int n=N; int m=M;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 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 |
0 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 |
0 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 |
0 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 |
0 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 |
1 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 |
0 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 |
1 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 |
0 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 |
1 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
