#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+1;
int cnt[N]={};
vector<int> tree[N];
int c[N]={};
int p[N]={};
int depth[N]={};
map<int, int> inside[1001];
map<int, int> supposed[1001];
bool cmp(map<int, int>& mp1, map<int, int>& mp2) {
if (mp1.size() != mp2.size()) return false;
for (auto it = mp1.begin(); it != mp1.end(); ++it) {
int key = it->first;
auto it2 = mp2.lower_bound(key);
if (it2 == mp2.end() || it2->first != key || it2->second != it->second) return false;
}
return true;
}
vector<vector<int>> by_depths(N);
bool ck(vector<int> sub) {
memset(cnt, 0, sizeof(cnt));
int sz = sub.size();
if (sz == 1) return true;
vector<int> depths(sz, 0);
vector<bool> matched(sz, false);
vector<int> now(sz, -1);
for (int i = 0; i < sz; ++i) {
inside[i].clear();
depths[i] = depth[sub[i]];
}
for (int i = depths[0]; i <= depths.back(); ++i) by_depths[i].clear();
for (int i = 0; i < sz; ++i) by_depths[depths[i]].push_back(sub[i]);
for (int i = 1; i < sz; ++i) {
int par = cnt[c[sub[i]]];
inside[par][c[sub[i]]]++;
if (depths[par] != depth[sub[i]]-1) return false;
cnt[c[sub[i]]]++;
}
for (int i = 0; i < sz; ++i) {
for (int j = 0; j < sz; ++j) {
if (matched[j]) continue;
if (depths[i] == depths[j] && cmp(inside[i], supposed[sub[j]])) {
matched[j] = true;
now[i] = j;
break;
}
}
if (now[i] == -1) return false;
}
for (int i = 1; i < sz; ++i) {
cnt[c[sub[i]]]--;
}
for (int i = 1; i < sz; ++i) {
int par = cnt[c[now[i]]];
if (p[now[i]] != now[par]) return false;
cnt[c[now[i]]]++;
}
return true;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
for (int i = 1; i < N; ++i) {
p[i] = P[i];
tree[i].push_back(p[i]);
tree[p[i]].push_back(i);
c[i] = C[i];
}
auto dfs = [&] (auto&& self, int v, int d=0) -> void {
depth[v] = d;
for (int u : tree[v]) if (u != p[v]) {
self(self, u, d+1);
}
};
dfs(dfs, 0);
vector<int> res(N);
for (int i = 0; i < N; ++i) {
for (int u : tree[i]) if (u != p[i]) {
supposed[i][c[u]]++;
}
}
for (int i = 0; i < N; ++i) {
vector<int> sub = {};
auto bfs = [&] (int s) -> void {
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
sub.push_back(v);
for (int u : tree[v]) if (u != p[v]) {
q.push(u);
}
}
};
bfs(i);
res[i] = ck(sub);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
2nd lines differ - on the 4th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Runtime error |
24 ms |
7284 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 8 |
Halted |
0 ms |
0 KB |
- |
