Submission #1016123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016123		JakobZorz	Beech Tree (IOI23_beechtree)	C++17	100 / 100	336 ms	188232 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;
}

// merge into s1
bool merge(set<pair<int,int>>&s1,set<pair<int,int>>&s2){
    bool res=true;
    for(auto i:s2){
        auto iter=s1.insert(i).first;
        auto iter2=iter,iter3=iter;
        if(iter3!=s1.begin()){
            iter3--;
            if(!good(iter->second,iter3->second))
                res=false;
        }
        
        iter2++;
        if(iter2!=s1.end()&&!good(iter2->second,iter->second))
            res=false;
    }
    return res;
}

set<pair<int,int>>get(int node){
    res[node]=!bad[node];
    set<pair<int,int>>s;
    s.insert({sub[node],node});
    for(int c:ch[node]){
        auto r=get(c);
        res[node]&=res[c];
        if(r.size()>s.size())
            swap(s,r);
        if(!merge(s,r))
            res[node]=false;
    }
    
    return s;
}

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: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12