Submission #1016080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016080		JakobZorz	Beech Tree (IOI23_beechtree)	C++17	26 / 100	2076 ms	57776 KiB

beechtree

#include"beechtree.h"
#include<algorithm>
#include<set>
#include<iostream>
#include<map>
#include<queue>
using namespace std;

int n;
vector<int>ch[200000];
map<int,int>ch_col[200000];
int par[200000];
int col[200000];
bool bad[200000];
int sub[200000];

void dfs1(int node){
    sub[node]=1;
    for(int c:ch[node]){
        dfs1(c);
        sub[node]+=sub[c];
    }
}

void dfs2(int node){
    bad[node]=ch[node].size()!=ch_col[node].size();
    for(int c:ch[node]){
        dfs2(c);
        bad[node]|=bad[c];
    }
}

bool get(int node){
    if(bad[node])
        return false;
    
    int cs=node;
    priority_queue<pair<int,int>>q;
    for(int c:ch[node])
        q.push({ch[c].size(),c});
    
    while(q.size()){
        int cn=q.top().second;
        q.pop();
        for(auto[c,i]:ch_col[cn])
            if(ch_col[cs][c]<i)
                return false;
        cs=cn;
        for(int c:ch[cn])
            q.push({ch[c].size(),c});
    }
    
    return true;
}

vector<int>beechtree(int N,int M,vector<int>P,vector<int>C){
    n=N;
    for(int i=0;i<n;i++)
        ch[i].clear();
    for(int i=0;i<n;i++){
        par[i]=P[i];
        if(i)
            ch[par[i]].push_back(i);
        col[i]=C[i];
    }
    dfs1(0);
    for(int i=0;i<n;i++){
        ch_col[i].clear();
        for(int c:ch[i])
            ch_col[i][col[c]]=sub[c];
    }
    dfs2(0);
    vector<int>res(n);
    for(int i=0;i<n;i++)
        res[i]=get(i);
    return res;
}

• 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