This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2e5 + 5;
constexpr int MAXM = 500 + 5;
vector<int> P, C;
vector<int> curr;
vector<int> permutato;
vector<bool> v;
vector<int> adj[MAXN];
int colori_usati[MAXM];
bool sol[MAXN];
void vediamo(int u) {
// cout << "vediamo " << u << '\n';
// colori_usati[C[u]] ++;
for (int i = 1; i < curr.size(); i ++) {
int f_i = colori_usati[C[permutato[i]]];
if (P[permutato[i]] != permutato[f_i]) return;
colori_usati[C[permutato[i]]] ++;
}
// cout << "permutazione : ";
// cout << "sol[u] = 1 !!" << '\n';
sol[u] = 1;
}
void generate_permutation(int u, int i) {
// cout << "permutazione u : " << u << " i : " << i << '\n';
if (sol[u]) return;
if (i == curr.size()) return vediamo(u);
for (int j = 0; j < curr.size(); j ++) {
if (v[j]) continue;
v[j] = 1;
permutato.push_back(curr[j]);
generate_permutation(u, i + 1);
permutato.pop_back();
v[j] = 0;
}
}
void check(int u) {
v.assign(curr.size(), 0);
permutato.push_back(u);
generate_permutation(u, 0);
}
void dfs(int u) {
// cout << "dfs " << u << '\n';
curr.push_back(u);
for (auto x : adj[u]) {
if (x == P[u]) continue;
dfs(x);
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
::P = P;
::C = C;
for (int i = 1; i < N; i ++) {
adj[P[i]].push_back(i);
adj[i].push_back(P[i]);
}
fill(sol, sol + N, 0);
for (int i = 0; i < N; i ++) {
// cout << "i : " << 0 << '\n';
curr.clear();
fill(colori_usati, colori_usati + MAXM, 0);
for (auto x : adj[i]) {
if (x == P[i]) continue;
dfs(x);
}
// cout << "fatto dfs: curr ";
// for (auto x : curr) cout << x << " ";
// cout << '\n';
// cout << "ora check" << '\n';
check(i);
}
vector<int> res(N);
for (int i = 0; i < N; i ++) res[i] = sol[i];
return res;
}
Compilation message (stderr)
beechtree.cpp: In function 'void vediamo(int)':
beechtree.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 1; i < curr.size(); i ++) {
| ~~^~~~~~~~~~~~~
beechtree.cpp: In function 'void generate_permutation(int, int)':
beechtree.cpp:33:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if (i == curr.size()) return vediamo(u);
| ~~^~~~~~~~~~~~~~
beechtree.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int j = 0; j < curr.size(); j ++) {
| ~~^~~~~~~~~~~~~
# | 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... |