Submission #1210146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210146		Nelt	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2098 ms	46992 KiB

beechtree

#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 cnt[N], ptr[N];
bool ok;
void dfs(ll v)
{
    for (ll to : g[v]) dfs(to);
    set<ll> s;
    for (ll to : g[v]) s.insert(c[to]);
    ok &= g[v].size() == s.size();
    cnt[c[v]]++;
}
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++)
    {
        priority_queue<array<ll, 3>> q;
        q.push({(ll)g[i].size(), 0, i});
        ll cur = 0;
        for (ll j = 1; j <= m; j++) cnt[j] = 0;
        ok = true;
        dfs(i);
        cnt[c[i]]--;
        for (ll j = 1; j <= m; j++) cur += cnt[j] > 0;
        vector<ll> ord;
        while (!q.empty())
        {
            auto [sz, id, v] = q.top();
            ord.push_back(v);
            q.pop();
            if (sz < cur)
            {
                ok = false;
                break;
            }
            for (ll to : g[v]) 
                cur -= cnt[c[to]]-- == 1, q.push({(ll)g[i].size(), (ll)ord.size(), to});
        }
        if (ok)
        {
            for (ll v : ord) 
                if (v != i)
                    ok &= p[v] == ord[cnt[c[v]]++];
        }
        ans.push_back(ok);
    }
    return ans;
}

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