Submission #1061810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061810		noyancanturk	Beech Tree (IOI23_beechtree)	C++17	22 / 100	220 ms	180132 KiB

beechtree

#include "beechtree.h"

#include <bits/stdc++.h>
using namespace std;

const int lim=2e5+100;

using pii=pair<int,int>;

#define pb push_back

int n,m;
vector<int>p,c;
int dep[lim];
vector<int>v[lim];
unordered_map<int,int>guycnt[lim],col[lim];
map<int,int>cnt[lim];

struct Node{
    int dep=0,chcnt=0,minch=0,maxch=0;
}dat[lim];

using pnode=Node*;

struct cmp{
    bool operator()(pnode i,pnode j) const {
        if(i->dep^j->dep)return i->dep<j->dep;
        if(i->chcnt^j->chcnt)return i->chcnt>j->chcnt;
        if(i->minch^j->minch)return i->minch>j->minch;
        return i->maxch>j->maxch;
    }
};

set<pnode,cmp>ct[lim];

bool insertnode(int par,pnode x){
    auto p=ct[par].insert(x).first;
    if(p!=ct[par].begin()){
        auto pp=prev(p);
        if((*pp)->chcnt<x->chcnt)return 0;
        if((*pp)->minch<x->minch)return 0;
        if((*pp)->maxch<x->maxch)return 0;
    }
    auto pp=next(p);
    if(pp!=ct[par].end()){
        if((*pp)->chcnt>x->chcnt)return 0;
        if((*pp)->minch>x->minch)return 0;
        if((*pp)->maxch>x->maxch)return 0;
    }
    return 1;
}

vector<int>dp;

void dfs(int node){
    for(int j:v[node]){
        dfs(j);
        if(!dp[j]){
            dp[node]=0;
        }
    }
    if(!dp[node])return;
    insertnode(node,dat+node);
    for(int j:v[node]){
        if(ct[node].size()<ct[j].size()){
            swap(ct[j],ct[node]);
        }
        for(pnode p:ct[j]){
            if(!insertnode(node,p)){
                dp[node]=0;
                return;
            }
        }
        if(col[node].size()<col[j].size()){
            swap(col[node],col[j]);
            swap(cnt[node],cnt[j]);
        }
        for(auto[x,y]:col[j]){
            if((--cnt[node][col[node][x]])==0){
                cnt[node].erase(col[node][x]);
            }
            cnt[node][col[node][x]+=y]++;
        }
        if(guycnt[node].size()<guycnt[j].size()){
            swap(guycnt[j],guycnt[node]);
        }
        for(auto[x,y]:guycnt[j]){
            guycnt[node][x]+=y;
        }
    }
    int have=col[node].size(),prevsum=0;
    for(auto[x,y]:cnt[node]){
        if(guycnt[node][have]!=x-prevsum){
            dp[node]=0;
            return;
        }
        have-=y;
        prevsum=x;
    }
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
    n=N,m=M;
    p=P,c=C;
    dp=vector<int>(n,1);
    for(int i=1;i<n;i++){
        v[P[i]].pb(i);
        if(col[P[i]].count(C[i]))dp[P[i]]=0;
        col[P[i]][c[i]]=1;
        cnt[p[i]][1]++;
    }
    for(int i=n-1;0<=i;i--){
        guycnt[i][v[i].size()]++;;
        dat[i].chcnt=v[i].size();
        if(dat[i].chcnt){
            dat[i].minch=INT_MAX;
            dat[i].maxch=0;
            for(int j:v[i]){
                dat[i].minch=min(dat[i].minch,dat[j].chcnt);
                dat[i].maxch=max(dat[i].maxch,dat[j].chcnt);
            }
        }
    }
    for(int i=1;i<n;i++){
        dep[i]=dep[p[i]]+1;
    }
    dfs(0);
    return dp;
}

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