Submission #1211283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211283		omsincoconut	Beech Tree (IOI23_beechtree)	C++17	18 / 100	2093 ms	24044 KiB

beechtree

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

using namespace std;

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    vector<int> ret(N);

    vector<vector<int>> child(N);
    for (int i = 1; i < N; i++) child[P[i]].push_back(i);

    for (int i = 0; i < N; i++) {
        bool can = true;

        map<int, int> cnt;
        priority_queue<tuple<int, int, int>> dt;
        vector<int> seq;
        
        dt.emplace(child[i].size(), -1, i);
        while (!dt.empty()) {
            auto [szu, ppu, u] = dt.top();
            dt.pop();
            seq.push_back(u);

            if (u != i) {
                can &= seq[cnt[C[u]]] == P[u];
                cnt[C[u]]++;
            }

            for (int v : child[u]) {
                dt.emplace(child[v].size(), -(int)seq.size(), v);
            }
        }

        // for (int u : seq) cout << u << " ";
        // cout << "\n";

        ret[i] = can;
    }

    return ret;
}

• 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