#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]);
}
vector<signed> ans2(ans.begin(), ans.end());
return ans2;
}
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:75: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]
75 | for (int j=0; j<relevant.size(); j++) {
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:109: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]
109 | vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
| ~^~~~~~~~~~~~~~~~
beechtree.cpp:116: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]
116 | 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;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
2 ms |
616 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
128 ms |
23800 KB |
Output is correct |
| 16 |
Correct |
135 ms |
22328 KB |
Output is correct |
| 17 |
Correct |
113 ms |
22736 KB |
Output is correct |
| 18 |
Correct |
116 ms |
23256 KB |
Output is correct |
| # |
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 |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 5 |
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 |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 5 |
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 |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 5 |
Halted |
0 ms |
0 KB |
- |
