제출 #1211297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211297		omsincoconut	참나무 (IOI23_beechtree)	C++17	18 / 100	2089 ms	17888 KiB

beechtree

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

using namespace std;

vector<int> normalize(vector<int> a) {
    vector<int> as = a;
    sort(as.begin(), as.end());
    for (int &i : a) i = lower_bound(as.begin(), as.end(), i) - as.begin();
    return a;
}

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

    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;

        vector<int> cnt(N);
        priority_queue<tuple<int, int, int>> dt;
        vector<int> seq;
        
        dt.emplace(child[i].size(), -1, i);
        while (!dt.empty()) {
            int szu, ppu, u;
            tie(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);
            }
        }

        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