| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1164556 | nai0610 | 참나무 (IOI23_beechtree) | C++20 | 0 ms | 0 KiB |
#include "beechtree.h"
#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =2e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int sz[maxn],par[maxn],b[maxn],cnt[maxn],col[maxn],res[maxn];
bool vs[maxn];
vector<int> g[maxn];
struct nai{
int s,id,u;
bool operator<(const nai& other) const {
return (s==other.s?id<other.id:s>other.s);
}
};
int get(int u,int p=-1) {
sz[u]=1;
for (auto v:g[u]) {
if (!vs[v]&&v!=p) sz[u]+=get(v,u);
}
return sz[u];
}
int find (int u,int s,int p=-1) {
for (auto v:g[u]) {
if (!vs[v]&&v!=p&&sz[v]*2>=s) return find(v,s,u);
}
return u;
}
int calc(int u){
vector<int> a;
set<nai> s;
s.insert({sz[u],0,u});
while (!s.empty()) {
int x=s.begin()->u;
s.erase(s.begin());
a.push_back(x);
for (auto v:g[x]) s.insert({sz[v],(int)a.size(),v});
}
for (int i=1;i<a.size();i++) {
int x=(i==1?0:cnt[col[a[i]]]);
if (par[a[i]]!=a[x]) return false;
cnt[col[a[i]]]++;
}
return true;
}
void nai(int u) {
int c=find(u,get(u));
vs[c]=1;
if (b[c]==-1){
b[c]=calc(c);
if (b[c]==0) {
for (int v=par[c];v&&b[v]==-1;v=par[v]) b[v]=0;
}
}
if (b[c]!=1) {
for (auto v:g[c]) nai(v);
}
if (par[c]&&!vs[par[c]]) nai(par[c]);
}
int[] beechtree(int n,int m,int[] p,int[] c){
for (int i=0;i<n;i++) {
col[i+1]=c[i];
par[i+1]=p[i]+1;
g[par[i+1]].push_back(i+1);
}
memset(b,-1,sizeof(b));
nai(1);
for (int i=1;i<=n;i++) {
if (b[i]==-1) b[i]=0;
res[i-1]=b[i];
}
return res;
}