#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void prmap(map<int,int> mp) {
for (auto i:mp) {
cout << i.first <<":"<<i.second<<", ";
}
cout << endl;
}
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};
int subtask2 = 1;
int subtask4 = 0;
map<int,int> freq;
for (int i=0; i<n; i++) {
freq[C[i]]++;
}
int ma = -1;
for (auto i:freq) ma=max(ma,i.second);
if (ma<=2) {
subtask4=1;
}
for (int i=1; i<n; i++) {
if (P[i]!=i-1) subtask2=0;
}
if (subtask2) {
vector<int> ans(n,0);
ans[n-1] = 1;
for (int i=n-2; i>=0; i--) {
ans[i] = ans[i+1] & (C[i]==C[i+1]);
}
return ans;
}
for (int i=n-1; i>=1; i--) {
subsize[P[i]]+=subsize[i];
for (int j:subtree[i]) {
subtree[P[i]].push_back(j);
if (subtask4 && subtree[P[i]].size()>700) {
break;
}
}
sons[P[i]].push_back(i);
}
vector<int> ans(n,1);
for (int root=0; root<n; root++) {
if (subtask4 && subsize[root]>=700) {
ans[root] = 0;
continue;
}
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]];
});
reverse(dep1.begin(), dep1.end());
map<int,int> colors;
int fail = 0;
for (int i=0; i<dep1.size(); i++) {
int node = dep1[i];
set<int> subbers;
map<int,int> colors2;
for (int j:sons[relevant[node]]) {
subbers.insert(C[j]);
if (i>0 && colors[C[j]]<subsize[j]) {
fail=1;
}
colors2[C[j]] = subsize[j];
}
colors=colors2;
if (subbers.size()<sons[relevant[node]].size()) {
fail=1;
}
//cout << "DOING " << root <<" " << i << " " << node << endl;
//prmap(colors);
}
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:53:16: error: could not convert 'ans' from 'vector<long long int>' to 'vector<int>'
53 | return ans;
| ^~~
| |
| vector<long long int>
beechtree.cpp:74: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]
74 | for (int j=0; j<relevant.size(); j++) {
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:108: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]
108 | vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:115: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]
115 | for (int i=0; i<dep1.size(); i++) {
| ~^~~~~~~~~~~~
beechtree.cpp:15:18: warning: unused variable 'm' [-Wunused-variable]
15 | int n=N; int m=M;
| ^
