Submission #1221337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221337		im2xtreme	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2092 ms	17108 KiB

beechtree

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include "beechtree.h"
using namespace std;

const int MAXN = 200005;

vector<int> tree[MAXN];

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    vector<int> result(N, 1);  // Assume beautiful

    // Build tree
    for (int i = 0; i < N; ++i) tree[i].clear();
    for (int i = 1; i < N; ++i) {
        tree[P[i]].push_back(i);
    }

    // Check each root
    for (int root = 0; root < N; ++root) {
        vector<int> perm;
        unordered_map<int, int> color_cnt;
        vector<int> pending;

        perm.push_back(root);

        for (int child : tree[root]) {
            pending.push_back(child);
        }

        bool ok = true;
        while (!pending.empty()) {
            bool added = false;

            for (int i = 0; i < (int)pending.size(); ++i) {
                int node = pending[i];
                int col = C[node];
                int f = color_cnt[col];

                if (f < (int)perm.size() && P[node] == perm[f]) {
                    perm.push_back(node);
                    color_cnt[col]++;
                    // Add this node’s children to pending
                    for (int child : tree[node]) {
                        pending.push_back(child);
                    }
                    // Erase this node from pending
                    pending.erase(pending.begin() + i);
                    added = true;
                    break;
                }
            }

            if (!added) {
                ok = false;
                break;
            }
        }

        if (!ok) {
            result[root] = 0;
        }
    }

    return result;
}

• 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