Submission #1233892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233892		Hanksburger	Beech Tree (IOI23_beechtree)	C++20	49 / 100	2096 ms	29896 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<pair<int, int>, int> > q;
vector<int> adj[200005], p, c, ans;
int sz[200005], n, m, t;
void calc(int u)
{
    sz[u]=1;
    for (int v:adj[u])
    {
        calc(v);
        sz[u]+=sz[v];
    }
}
int solve(int x)
{
    //cout << "solve " << x << '\n';
    vector<int> perm, mp(n, 0), freq(m+1, 0);
    q.push({{sz[x], t=0}, x});
    while (!q.empty())
    {
        int u=q.top().second;
        q.pop();
        mp[u]=perm.size();
        perm.push_back(u);
        //cout << "perm " << u << '\n';
        for (int v:adj[u])
            q.push({{sz[v], --t}, v});
    }
    for (int i=1; i<perm.size(); i++)
    {
        if (mp[p[perm[i]]]!=(freq[c[perm[i]]]++))
            return 0;
        //cout << "check ok " << i << '\n';
    }
    return 1;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
    n=N, m=M, p=P, c=C;
    for (int i=1; i<n; i++)
        adj[p[i]].push_back(i);
    calc(0);
    for (int i=0; i<n; i++)
        ans.push_back(solve(i));
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12