Submission #846570

#	Time	Username	Problem	Language	Result	Execution time	Memory
846570		dlalswp25	Beech Tree (IOI23_beechtree)	C++17	18 / 100	2007 ms	30148 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int> piii;

int N, M;
vector<int> adj[202020];
vector<int> P, C;
int cnt[202020];
int idx[202020];
vector<int> V;
int D[202020];
int deg[202020];

void dfs(int v) {
    V.push_back(v);
    for (int i : adj[v]) dfs(i);
}

bool solve(int rt) {
    for (int i = 1; i <= M; i++) cnt[i] = 0;
    V.clear();
    dfs(rt);
    for (int i : V) {
        D[i] = 0;
        deg[i] = adj[i].size();
    }

    {
        priority_queue<piii, vector<piii>, greater<piii>> pq;
        for (int i : V) {
            if (!deg[i]) pq.emplace(0, 0, i);
        }
        int bef = -1;
        while (pq.size()) {
            int x = get<2>(pq.top()); pq.pop();
            if (bef != -1 && adj[bef].size() < adj[x].size()) D[x] = max(D[x], D[bef] + 1);
            if (x != rt) {
                deg[P[x]]--;
                D[P[x]] = max(D[P[x]], D[x] + 1);
                if (!deg[P[x]]) pq.emplace(adj[P[x]].size(), D[P[x]], P[x]);
            }
            bef = x;
        }
    }

    priority_queue<tuple<int, int, int, int>> pq;
    pq.emplace(D[rt], 0, 0, rt);
    int id = 0;
    while (pq.size()) {
        int x = get<3>(pq.top()); pq.pop();
        idx[x] = id++;
        if (x != rt && cnt[C[x]]++ != idx[P[x]]) return false;
        for (int i : adj[x]) pq.emplace(adj[i].size(), D[i], -idx[x], i);
    }
    return true;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    ::N = N; ::M = M; ::P = P; ::C = C;
    vector<int> ans(N);
    for (int i = 1; i < N; i++) adj[P[i]].push_back(i);
    for (int i = 0; i < N; i++) ans[i] = solve(i);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 9 / 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