#include "beechtree.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
const ll N = 2e5 + 5;
vector<ll> g[N];
vector<int> ans;
ll c[N], p[N];
ll last[N], ptr[N], sub[N];
vector<pair<ll, ll>> freq[N];
map<ll, ll> col[N];
vector<ll> ord;
bool ok;
void dfs(ll v)
{
sub[v] = 1;
for (ll to : g[v])
dfs(to), sub[v] += sub[to], col[v][c[to]] = sub[to];
ord.push_back(v);
ok &= g[v].size() == col[v].size();
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C)
{
for (ll i = 1; i <= n; i++)
p[i] = P[i - 1] + 1, c[i] = C[i - 1];
for (ll i = 2; i <= n; i++)
g[p[i]].push_back(i);
{
vector<ll> b;
for (ll i = 1; i <= n; i++)
b.push_back(c[i]);
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
for (ll i = 1; i <= n; i++)
c[i] = lower_bound(b.begin(), b.end(), c[i]) - b.begin();
m = b.size() - 1;
}
for (ll i = 1; i <= n; i++)
{
ok = true;
for (ll i = 1; i <= n; i++) col[i].clear();
for (ll j = 1; j <= m; j++)
freq[j].clear();
ord.clear();
dfs(i);
sort(ord.begin(), ord.end(), [&](ll a, ll b)
{ return sub[a] >= sub[b]; });
for (ll i = 0; i + 1 < ord.size(); i++)
if (sub[ord[i]] == sub[ord[i + 1]])
ok &= col[ord[i]] == col[ord[i + 1]];
else
{
for (auto [a, b] : col[ord[i]]) ok &= !col[ord[i + 1]].count(a) or col[ord[i + 1]][a] <= b;
for (auto [a, b] : col[ord[i + 1]]) ok &= col[ord[i]].count(a) and col[ord[i]][a] >= b;
}
ans.push_back(ok);
}
return ans;
}
# | 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... |