This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
vector<multiset<pair<int, map<int, int>>>> c(N);
vector<vector<int>> g(N);
vector<int> ans(N, 1), sz(N, 1), len(N);
for(int i=1; i<N; i++){
g[P[i]].push_back(i);
}
auto check = [&](auto a, auto b){
bool ok = a.size() >= b.size();
for(auto [k, v]:b){
ok &= a[k]>=v;
}
return ok;
};
auto add = [&](auto p, auto u){
len[u]+=p.second.size();
bool ok = 1;
auto it = c[u].insert(p);
if(next(it)!=c[u].end()){
ok&=check(next(it)->second, it->second);
}
if(it!=c[u].begin()){
ok&=check(it->second, prev(it)->second);
}
return ok;
};
function<void(int)> dfs = [&](int u){
map<int, int> cur;
for(auto v:g[u]){
dfs(v);
sz[u]+=sz[v];
ans[u]&=ans[v];
ans[u]&= !cur.count(C[v]);
cur[C[v]] = sz[v];
if(len[u] < len[v]){
swap(c[u], c[v]);
}
// insert
for(auto p:c[v]){
ans[u]&=add(p, u);
}
}
ans[u]&=add(make_pair(sz[u], cur), u);
};
dfs(0);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |