#include "beechtree.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define mii map<int,int>
#define pii pair<int,int>
#define vpii vector<pii>
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vb vector<bool>
using namespace std;
vector<vi>adj, colset, su;
vi dep, sts, die, diesum, tp;
vector<signed>ans;
int dfs(int node){
int cur = 1;
for(auto u : adj[node]){
dep[u] = dep[node] + 1;
cur += dfs(u);
}
sts[node] = cur;
return cur;
}
int d2(int node){
int cur = die[node];
for(auto u : adj[node]){
cur += d2(u);
}
diesum[node] = cur;
return cur;
}
void d3(int node){
if(sts[node] == 1){
su[node][tp[node]]++; return;
}
for(auto u : adj[node]){
f0r(j, 4){
su[node][j] += su[u][j];
}
}
su[node][tp[node]]++;
}
void solve(int node){
if(sts[node] == 1){
ans[node] = 1; return;
}
for(auto u : adj[node]){
solve(u);
}
if(diesum[node] != 0){
ans[node] = 0; return;
}
for(auto u : adj[node]){
if(ans[u] == 0){
ans[node] = 0; return;
}
}
vi w = su[node];
if(tp[node] == 1 && w[3] != 0){
ans[node] = 0; return;
}
if(tp[node] == 2 && w[3] != 0){
ans[node] = 0; return;
}
if(w[1] != 0 && w[2] != 0){
ans[node] = 0; return;
}
ans[node] = 1; return;
}
std::vector<signed> beechtree(signed N, signed M, std::vector<signed> P, std::vector<signed> C)
{
ans.resize(N);
FOR(i, 1, N)ans[i] = 0;
colset.clear(); colset.resize(N); adj.clear(); adj.resize(N); tp.clear(); tp.resize(N);
dep.clear(); dep.resize(N); sts.clear(); sts.resize(N); die.clear(); die.resize(N); diesum.clear(); diesum.resize(N);
FOR(i, 1, N){
adj[P[i]].pb(i);
}
f0r(i, N){
set<int>tmp;
for(auto u : adj[i]){
tmp.insert(C[u]); colset[i].pb(C[u]);
}
if(tmp.size() != colset[i].size()){
die[i] = 1;
}
int sum = 0;
for(auto u : tmp){
sum += u;
}
tp[i] = sum;
}
dfs(0);
d2(0);
su.resize(N);
f0r(i, N){
su[i].resize(4);
}
d3(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... |