Submission #842201

#	Time	Username	Problem	Language	Result	Execution time	Memory
842201		ainta	Beech Tree (IOI23_beechtree)	C++17	100 / 100	247 ms	88932 KiB

beechtree

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

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}

#define N_ 201000
int n, m, w[N_], CC[N_],par[N_], CK[N_], Num[N_];
vi E[N_];
vi ans;
map<int,int>D[N_],  G[N_];

void DFS(int a){
    CC[a]=1;
    set<int>Set;
    for(auto &x:E[a]){
        DFS(x);
        Set.insert(w[x]);
        CC[a]+=CC[x];
    }
    if(si(Set) != si(E[a])){
        CK[a]=1;
    }
}
int Go(int a){
    if(!si(E[a])){
        Num[a] = a;
        D[a][CC[a]] = a;
        return 1;
    }
    for(auto &t:E[a]){
        ans[t] = Go(t);
        //printf("%d %d\n",t,ans[t]);
    }
    if(CK[a]){
        return 0;
    }
    int x = -1, Mx = -1;
    for(auto &t:E[a]){
        if(!ans[t])return 0;
        if(Mx <CC[t]){
            Mx=CC[t];
            x=t;
        }
    }
    int px = Num[x];
    Num[a]=px;
    for(auto &y:E[a]){
        if(y==x)continue;
        int py = Num[y];
        for(auto &[c,u] : D[py]){
            if(c==1)continue;
            auto it = D[px].lower_bound(c);
            int v = it->se;
            int vv;
            if(it->fi == c)vv = v;
            else{
                it--;
                vv=it->se;
            }
            for(auto &z: E[u]){
                if(!G[v].count(w[z]) || CC[G[v][w[z]]] < CC[z])return 0;
            }
            for(auto &z: E[vv]){
                if(!G[u].count(w[z]) || CC[G[u][w[z]]] < CC[z])return 0;
            }
        }
        for(auto &[c,u] : D[py]){
            D[px][c]=u;
        }
    }
    auto it = D[px].end();it--;
    int u = it->se;
    for(auto &z: E[u]){
        if(!G[a].count(w[z]) || CC[G[a][w[z]]] < CC[z])return 0;
    }
    D[px][CC[a]]=a;
    return 1;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n=N, m=M;
    ans.resize(n);
    rep(i,n){
        CK[i]=0;
        E[i].clear();
    }
    map<int,int>Map;
    int c=0;
    rng(i,1,n-1){
        par[i]=P[i];
        E[P[i]].pb(i);
        if(!Map.count(C[i])){
            Map[C[i]]=++c;
        }
    }
    m=c;
    rng(i,1,n-1){
        C[i]=Map[C[i]];
        w[i]=C[i];
        G[P[i]][w[i]]=i;
    }
    DFS(0);
    ans[0] = Go(0);

    return ans;
}

• 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