Submission #1221133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221133		trimkus	Beech Tree (IOI23_beechtree)	C++20	66 / 100	2098 ms	69508 KiB

beechtree

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************
* 
*/
//#define DEBUG
#ifndef DEBUG
#include "beechtree.h"
#endif
#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> sz(N,1);
    auto dfs = [&](auto& dfs, int node) -> void {
        /// << node << " = ";
        bool ok = true;
        res[node] = 1;
        for (auto& u : adj[node]) {
            dfs(dfs, u);
            sz[node]+=sz[u];
        }
        for (auto& u : adj[node]) {
            if (!res[u]) {
                res[node] = 0;
                return;
            }
        }
        vector<int> ord;
        priority_queue<std::array<int, 3> >pq;
        pq.push({sz[node],-(int)ord.size(),node});
        while(pq.size()){
            int v =pq.top()[2];
            pq.pop();
            ord.push_back(v);
            for(int x : adj[v]){
                pq.push({sz[x],-(int)ord.size(),x});
            }
        }
        map<int, int> cnt;
        int need = 0;
        #ifdef DEBUG
        cout << "at node = " << node << ":\n";
        #endif
        for (auto i : ord) {
            #ifdef DEBUG
            cout << " node = " << i << ", with color = " << C[i] << ", need = " << need << "\n";
            #endif
            if(need++==0)continue;
            int p = ord[cnt[C[i]]++];
            if(p!=P[i]){
                res[node]=0;
                break;
            }
        }
    };
    dfs(dfs, 0);
    return res;
}
#ifdef DEBUG
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>p(n),c(n);
    for(int&x:p)cin>>x;
    for(int&x:c)cin>>x;
    for(auto x:beechtree(n,m,p,c)){
        cout << x << " ";
    }
}
#endif

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