Submission #1074749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074749		Unforgettablepl	Beech Tree (IOI23_beechtree)	C++17	26 / 100	2095 ms	19532 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> ans(N);
    vector<vector<int>> adj(N);
    for(int i=1;i<N;i++)adj[P[i]].emplace_back(i);
    auto check = [&](int root){
        map<int,int> cnt;
        priority_queue<tuple<int,int,int>> q;
        vector seq = {root};
        for(int&i:adj[root])q.emplace(adj[i].size(),0,i);
        while(!q.empty()) {
            auto [a,b,curr] = q.top();q.pop();
            if(seq[cnt[C[curr]]]!=P[curr])return false;
            cnt[C[curr]]++;
            seq.emplace_back(curr);
            for(int&i:adj[curr])q.emplace(adj[i].size(),-(seq.size()-1),i);
        }
        return true;
    };
    for(int i=0;i<N;i++)if(check(i))ans[i]=1;
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 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