#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct obj{
ll i,d;
set<ll> s;
bool operator<(const obj &o){
return d!=o.d?d<o.d:s.size()>o.s.size();
}
bool nxt(const obj &o){
for(ll i : o.s){
if (!s.count(i)){
return false;
}
}
return true;
}
};
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
ll n = N;
{
vector<ll> ans(n);
ans[n-1] = ans[n-2] = 1;
for(ll i = n-3;i>=0;i--){
ans[i] = ans[i+1]&&(C[i+2]==C[i+1]);
}
return ans;
}
ll m = M;
vector<vector<ll>> ch(n);
for(ll i = 1;i<n;i++) ch[P[i]].push_back(i);
vector<ll> h(n,0),d(n,0);
{
function<void(ll)> dfs;
dfs = [&](ll i){
for(ll j : ch[i]) {
d[j] = d[i]+1;
dfs(j);
h[i] = max(h[i],h[j]+1);
}
};
dfs(0);
}
vector<ll> bad(n,0);
for(ll i = n-1;i>=0;i--){
vector<ll> v;
for(ll j : ch[i]){
if (bad[j]) bad[i] = 1;
v.push_back(C[j]);
if(ch[i].size()<ch[j].size()) bad[i] = 1;
}
sort(v.begin(),v.end());
if (unique(v.begin(),v.end())!=v.end()) bad[i] = 1;
}
vector<ll> ans(n,0);
for(ll i = 0;i<n;i++){
if (bad[i]) continue;
if (h[i]<=1) {
ans[i] = 1;
continue;
}
/*vector<obj> cur;
function<void(ll)> dfs;
dfs = [&](ll i){
if (ch[i].empty()) return;
obj o = {i,d[i]};
for(ll j : ch[i]){
o.s.insert(C[j]);
}
cur.push_back(o);
for(ll j : ch[i]){
dfs(j);
}
};
dfs(i);
sort(cur.begin(),cur.end());
ll res = 1;
for(ll i = 0;i+1<cur.size();i++){
if (!cur[i].nxt(cur[i+1])){
res = 0;
break;
}
}
ans[i] = res;*/
ll ok = 1;
vector<ll> v;
function<void(ll)> dfs;
dfs = [&](ll i){
v.push_back(i);
for(ll j : ch[i]){
dfs(j);
}
};
dfs(i);
ll cur = 0;
do{
map<ll,ll> cnt;
ll y = 1;
for(ll i = 1;i<v.size();i++){
if (v[cnt[C[v[i]]]]!=P[v[i]]) y = 0;
cnt[C[v[i]]]++;
}
cur |= y;
}while(next_permutation(v.begin()+1,v.end()));
ans[i] = cur;
}
return ans;
}
Compilation message
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:101:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(ll i = 1;i<v.size();i++){
| ~^~~~~~~~~
beechtree.cpp:87:12: warning: unused variable 'ok' [-Wunused-variable]
87 | ll ok = 1;
| ^~
beechtree.cpp:31:8: warning: unused variable 'm' [-Wunused-variable]
31 | ll m = M;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
38 ms |
4176 KB |
Output is correct |
| 8 |
Correct |
46 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
500 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
36 ms |
6592 KB |
Output is correct |
| 18 |
Correct |
38 ms |
6740 KB |
Output is correct |
| 19 |
Correct |
44 ms |
6700 KB |
Output is correct |
| 20 |
Correct |
44 ms |
6736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
