# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1221333 | im2xtreme | Beech Tree (IOI23_beechtree) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <unordered_map>
#include "beechtree.h"
using namespace std;
const int MAXN = 200005;
vector<int> tree[MAXN];
int P[MAXN], C[MAXN];
int result[MAXN];
void collect_subtree(int u, vector<int>& nodes) {
nodes.push_back(u);
for (int v : tree[u]) {
collect_subtree(v, nodes);
}
}
bool is_beautiful(int root) {
vector<int> nodes;
collect_subtree(root, nodes);
if (nodes[0] != root) return false;
unordered_map<int, int> color_count;
for (int i = 1; i < (int)nodes.size(); ++i) {
int curr = nodes[i];
int color = C[curr];
int f = color_count[color];
if (f >= i || P[curr] != nodes[f]) return false;
color_count[color]++;
}
return true;
}
int* beechtree(int N, int M, int* p, int* c) {
for (int i = 0; i < N; ++i) {
tree[i].clear();
}
for (int i = 1; i < N; ++i) {
tree[p[i]].push_back(i);
}
for (int i = 0; i < N; ++i) {
P[i] = p[i];
C[i] = c[i];
}
for (int i = 0; i < N; ++i) {
result[i] = is_beautiful(i) ? 1 : 0;
}
return result;
}