#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200'000;
vector<pair<int, int>> grafo[MAXN], opz[MAXN];
int m, col[MAXN], p[MAXN];
bool ok[MAXN];
/*
void dfs(int nodo) {
ok[nodo] = false;
for (auto [to, c] : grafo[nodo]) {
dfs(to);
opz[nodo].emplace_back(to, c);
for (auto [nod, c] : opz[to]) {
opz[nodo].emplace_back(nod, c);
}
}
sort(opz[nodo].begin(), opz[nodo].end());
do {
vector<int> cont(m + 1, 0);
auto tmp = opz[nodo];
tmp.insert(tmp.begin(), {nodo, 0});
bool flag = true;
for (int i = 1; i < tmp.size(); i++) {
if (tmp[cont[tmp[i].second]].first != p[tmp[i].first])flag = false;
cont[tmp[i].second]++;
}
ok[nodo] |= flag;
} while (next_permutation(opz[nodo].begin(), opz[nodo].end()));
//cout<<nodo<<" "<<col[nodo]<<"\n";
}
*/
map<int,int> freq[MAXN];
int num[MAXN];
bool comp(pair<int,int> x,pair<int,int> y){
return num[x.first]>num[y.first];
}
void dfs(int nodo){
vector<int> tmp;
for(auto [to,c] : grafo[nodo]){
dfs(to);
num[nodo]+=num[to]+1;
tmp.push_back(c);
freq[nodo][c]++;
}
sort(tmp.begin(),tmp.end());
sort(grafo[nodo].begin(),grafo[nodo].end(),comp);
ok[nodo]=true;
for(int i=1;i<tmp.size();i++){
if(tmp[i]==tmp[i-1])ok[nodo]=false;
}
for(int i=0;i<grafo[nodo].size();i++){
int curr = grafo[nodo][i].first;
int prev = (i==0 ? nodo : grafo[nodo][i-1].first);
for(auto [x,y] : freq[curr]){
if(y>freq[prev][x])ok[nodo]=false;
}
}
for(auto [to,c] : grafo[nodo]){
for(auto [x,y] : freq[to]){
freq[nodo][x]+=y;
}
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
m = M;
for (int i = 1; i <= N - 1; i++) {
grafo[P[i]].emplace_back(i, C[i]);
p[i] = P[i];
}
dfs(0);
vector<int> ans;
for (int i = 0; i < N; i++) {
ans.push_back(ok[i]);
}
return ans;
}
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> P(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &P[i]));
std::vector<int> C(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &C[i]));
fclose(stdin);
std::vector<int> res = beechtree(N, M, P, C);
int n = res.size();
for (int i = 0; i < n; ++i) {
if (i > 0)
printf(" ");
printf("%d", res[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
Compilation message
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=1;i<tmp.size();i++){
| ~^~~~~~~~~~~
beechtree.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<grafo[nodo].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccvY1GeV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc14K9nU.o:beechtree.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
