Submission #1016097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016097		JakobZorz	참나무 (IOI23_beechtree)	C++17	66 / 100	2031 ms	173908 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];
bool res[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 good(int a,int b){
    for(auto[c,i]:ch_col[b])
        if(ch_col[a][c]<i)
            return false;
    return true;
}

void get(int node){
    for(int c:ch[node])
        get(c);
    
    if(bad[node]){
        res[node]=false;
        return;
    }
    
    int cs=node;
    priority_queue<pair<int,int>>q;
    for(int c:ch[node])
        q.push({sub[c],c});
    
    while(q.size()){
        int cn=q.top().second;
        q.pop();
        if(!good(cs,cn)){
            res[node]=false;
            return;
        }
        
        cs=cn;
        for(int c:ch[cn])
            q.push({sub[c],c});
    }
    
    res[node]=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);
    
    get(0);
    
    vector<int>res2(n);
    for(int i=0;i<n;i++)
        res2[i]=res[i];
    return res2;
}

• 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