# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1241563 | SalihSahin | 참나무 (IOI23_beechtree) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "beechtree.h"
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
vector<int> perm;
vector<pair<int, int> > edges;
void dfs(int node){
perm.pb(node);
for(auto itr: ch[node]){
edges.pb(itr);
dfs(itr.first);
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
vector<int> cnt(M+1);
vector<int> ans(N, 1);
for(int i = 0; i < N; i++){
perm.clear();
edges.clear();
dfs(i);
sort(perm.begin(), perm.end());
bool check = 0;
vector<int> cnt(M);
do{
if(perm[0] != i) continue;
vector<int> pos(N);
for(int j = 0; j < perm.size(); j++){
pos[perm[j]] = j;
}
bool yes = 1;
for(int j = 1; j < perm.size(); j++){
if(pos[P[perm[j]]] != cnt[C[perm[j]]]) yes = 0;
cnt[C[perm[j]]]++;
}
check |= yes;
}while(next_permutation(perm.begin(), perm.end()));
ans[i] = check;
}
return ans;
}