Submission #1220910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220910		trimkus	Beech Tree (IOI23_beechtree)	C++20	17 / 100	2094 ms	78232 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
// #define DEBUG
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    set<int> level1;
    int col = -1;
    vector<int> res(N);
    vector<vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        adj[P[i]].push_back(i);
    }
    vector<int> ord;
    auto dfs = [&](auto& dfs, int node) -> void {
        // cerr << node << " = ";
        bool ok = true;
        res[node] = 1;
        for (auto& u : adj[node]) {
            dfs(dfs, u);
        }
        for (auto& u : adj[node]) {
            if (!res[u]) {
                res[node] = 0;
                return;
            }
        }
        vector<array<int, 3>> ord;
        queue<array<int, 2>> q;
        q.push({node, 0});
        while (q.size()) {
            int v = q.front()[0];
            int d = q.front()[1];
            if (adj[v].size() > 0) ord.push_back({d, (int)-adj[v].size(), v});
            q.pop();
            for (auto& u : adj[v]) {
                q.push({u, d + 1});
            }
        }
        sort(begin(ord), end(ord));
        map<int, int> cnt;
        int need = 0;
        #ifdef DEBUG
        cerr << "at node = " << node << ":\n";
        #endif
        for (auto [d, s, i] : ord) {
            #ifdef DEBUG
            cerr << d << " " << -s << " node = " << i << ", with color = " << C[i] << ", need = " << need << "\n";
            #endif
            for (auto& u : adj[i]) {
                if (cnt[C[u]] != need) {
                    res[node] = 0;
                    return;
                }
                cnt[C[u]] += 1;
            }
            if (adj[i].size() > 0) need += 1;
        }
    };
    dfs(dfs, 0);
    return res;
}

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