#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
int n , m , p[N] , cnt[N] , c[N];
vector<int> sub[N];
vector<int> solve(){
for(int i = 1; i <= n; i++){
int x = p[i];
while(x > 0){
sub[x].push_back(i);
x = p[x];
}
}
vector<int> ans(n,0);
for(int v = 1; v <= n; v++){
sort(all(sub[v]));
while(next_permutation(all(sub[v]))){
int ok = 1;
// cout << v << "\n";
for(int j = 0; j < sub[v].size(); j++){
int u = sub[v][j];
if(cnt[c[u]] == 0){
if(p[u] != v) ok = 0;
} else {
if(p[u] != sub[v][cnt[c[u]]-1]) ok = 0;
}
cnt[c[u]]++;
}
for(int j = 0; j < sub[v].size(); j++){
int u = sub[v][j];
cnt[c[u]]--;
}
if(ok == 1){
ans[v-1] = 1;
}
}
if(1){
sort(all(sub[v]));
int ok = 1;
for(int j = 0; j < sub[v].size(); j++){
int u = sub[v][j];
if(cnt[c[u]] == 0){
if(p[u] != v) ok = 0;
} else {
if(p[u] != sub[v][cnt[c[u]]-1]) ok = 0;
}
cnt[c[u]]++;
}
for(int j = 0; j < sub[v].size(); j++){
int u = sub[v][j];
cnt[c[u]]--;
}
if(ok == 1){
ans[v-1] = 1;
}
}
if(sub[v].size() == 0) ans[v-1] = 1;
}
return ans;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
n = N; m = M;
for(int i = 0; i < P.size(); i++){
p[i+1] = P[i]+1;
c[i+1] = C[i];
}
return solve();
}
// int main()
// {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> P(N);
// for (int i = 0; i < N; ++i)
// assert(1 == scanf("%d", &P[i]));
// std::vector<int> C(N);
// for (int i = 0; i < N; ++i)
// assert(1 == scanf("%d", &C[i]));
//
// fclose(stdin);
//
// std::vector<int> res = beechtree(N, M, P, C);
//
// int n = res.size();
// for (int i = 0; i < n; ++i)
// {
// if (i > 0)
// printf(" ");
// printf("%d", res[i]);
// }
// printf("\n");
// fclose(stdout);
//
// return 0;
// }
//
# | 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... |