#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using pii = pair<int, int>;
using piii = tuple<int, int, int>;
vector<int> T[202020], C;
priority_queue<piii> Q;
int S[202020], I[202020];
set<pii> P1[202020];
set<piii> P2[202020];
int n, m;
bool dfs(int u, vector<int> &A) {
bool f = 1;
P1[u].emplace(I[u], u);
for (int &v: T[u]) {
auto it = P2[u].emplace(C[v], I[v], u).first;
if (it != P2[u].begin() && get<0>(*prev(it)) == C[v]) f = 0;
if (next(it) != P2[u].end() && get<0>(*next(it)) == C[v]) f = 0;
}
for (int &v: T[u]) {
f &= dfs(v, A);
if (P1[u].size() < P1[v].size()) {
swap(P1[u], P1[v]); swap(P2[u], P2[v]);
}
for (auto [i, w]: P1[v]) {
auto it1 = P1[u].emplace(i, w).first;
for (int &x: T[w]) {
auto it2 = P2[u].emplace(C[x], I[x], x).first;
if (next(it2) != P2[u].end() && get<0>(*next(it2)) == C[x]) {
if (next(it1) == P1[u].end() || next(it1)->second != get<2>(*next(it2))) f = 0;
}
if (it1 != P1[u].begin()) {
if (it2 == P2[u].begin() || get<0>(*prev(it2)) != C[x] \
|| get<2>(*prev(it2)) != prev(it1)->second) f = 0;
}
}
}
}
return A[u] = f;
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
::C = C; ::n = n; ::m = m;
int i;
for (i = 1; i < n; i++) {
T[P[i]].push_back(i);
}
fill(S, S + n, 1);
for (i = n - 1; i >= 1; i--) {
S[P[i]] += S[i];
}
Q.emplace(S[0], 0, 0);
for (i = 0; !Q.empty(); i++) {
auto [_, j, v] = Q.top();
I[v] = i; Q.pop();
for (int &w: T[v]) {
Q.emplace(S[w], i, w);
}
}
vector<int> A(n);
dfs(0, A);
return A;
}
Compilation message
beechtree.cpp: In function 'bool dfs(int, std::vector<int>&)':
beechtree.cpp:46:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
46 | return A[u] = f;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25692 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25688 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25688 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 4 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 5 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 6 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 7 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
25692 KB |
2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25688 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25692 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25688 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25692 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25692 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25688 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25688 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
25692 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
