| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 857476 | mychecksedad | 참나무 (IOI23_beechtree) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <beechtree.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5+100;
int sz[N], dep[N], par[N], n;
vector<array<int, 2>> g[N], s[N];
vector<int> ans, COL;
set<int> C[N];
void dfs(int v){
ans[v] = 1;
sz[v] = 1;
s[v].pb({v, COL[v]});
for(auto U: g[v]){
int u = U[0], c = U[1];
dep[u] = dep[v] + 1;
par[u] = v;
dfs(u);
for(auto x: s[u]) s[v].pb(x);
sz[v] += sz[u];
ans[v] &= ans[u];
if(C[v].find(c) != C[v].end()) ans[v] = 0;
C[v].insert(c);
}
if(n <= 8){
sort(s[v].begin() + 1, s[v].end());
ans[v] = 0;
do{
bool ok = 1;
map<int, int> colptr;
for(int i = 1; i < s[v].size(); ++i){
int u = s[v][i][0], co = s[v][i][1];
if(par[u] != s[v][colptr[co]][0]){
ok = 0;
break;
}
colptr[co]++;
}
if(ok){
ans[v] = 1;
break;
}
}while(next_permutation(s[v].begin() + 1, s[v].end()));
}
else{
if(ans[v] == 0) return;
sort(all(g[v]), [&](const array<int, 2> &x, const array<int, 2> &y){
return sz[x[0]] > sz[y[0]];
});
for(int i = 0; i < g[v].size(); ++i){
int x = (i == 0 ? v : g[v][i - 1][0]), y = g[v][i][0];
for(auto col: C[y]){
if(C[x].find(col) == C[x].end()){
ans[v] = 0;
break;
}
}
}
if(g[v].size() > 1){
if(abs(dep[g[v][0][0]] - dep[g[v][1][0]]) > 1) ans[v] = 0;
}
if(ans[v] == 0) return;
if(g[v].size() == 0){
s[v].pb({v, COL[v]});
return;
}
if(g[v].size() == 1){
s[v].pb({v, COL[v]});
for(auto u: s[g[v][0][0]]) s[v].pb(u);
return;
}
int ptx = 0, pty = 0;
array<int, 2> pt = {0, 0};
s[v].pb(v);
int x = g[v][0][0], y = g[v][1][0];
int num = s[x].size() + s[y].size();
while(num > 0){
if(ptx == g[x].size()){
s[v].pb({s[y][pty]});
pty++;
}else if(pty == g[y].size()){
s[v].pb({s[x][ptx]});
ptx++;
}else{
if(pt[0] < pt[1]){
}else{
}
}
int col = s[v].back()[1] - 1, node = s[v].back()[0];
if(s[v][pt[col]][0] != par[node]){
ans[v] = 0;
return;
}
num--;
}
}
}
vector<int> beechtree(int nn, int m, vector<int> P, vector<int> CC){
COL = CC;
n = nn;
for(int i = 1; i < n; ++i){
g[P[i]].pb({i, COL[i]});
}
ans.resize(n);
dep[0] = 0;
dfs(0);
return ans;
}