Submission #1143935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143935		Math4Life2020	Beech Tree (IOI23_beechtree)	C++20	31 / 100	85 ms	79320 KiB

beechtree

#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

const ll Nm = 2e5+5;
vector<bool> ans(Nm,1);
vector<ll> radj,C;
vector<ll> fadj[Nm];
ll clen[Nm]; //0 -> leaf, 1 -> leaf+1 edge, 2 -> longer 
ll col2[Nm]; //color of the 2
ll lbot[Nm]; //location of bottom
set<ll> clin[Nm];
ll N,M;

void dfs(ll x) {
    for (ll y: fadj[x]) {
        dfs(y);
        if (ans[y]==0) {
            ans[x]=0;
        }
    }
    if (ans[x]==0) {
        return;
    }
    if (fadj[x].size()==0) {
        clen[x]=0;
        ans[x]=1;
        return;
    }
    clen[x]=1;
    ll n1in = 0; //number of >=1s in fadj[x]
    ll n2in = 0; //number of >=2s in fadj[x]
    for (ll y: fadj[x]) {
        clin[x].insert(C[y]);
        if (clen[y]>=1) {
            n1in++;
        }
        if (clen[y]>=2) {
            n2in++;
        }
    }
    if (clin[x].size()!=fadj[x].size() || n2in>=2) {
        ans[x]=0;
        return;
    }
    if (n1in>=2 && radj[x]!=-1) {
        ans[radj[x]]=0;
    }
    if (n2in==0) {
        if (n1in==0) {
            //only leaves in then
            ans[x]=1; //will retrieve later
        } else if (n1in==1) {
            clen[x]=2;
            set<ll> cprev;
            ll yc = -1;
            for (ll y: fadj[x]) {
                if (clen[y]==1) {
                    yc=y;
                }
            }
            assert(yc!=-1);
            col2[x]=C[yc];
            lbot[x]=yc;
            for (ll c0: clin[yc]) {
                if (clin[x].find(c0)==clin[x].end()) {
                    ans[x]=0;
                    return;
                }
            }
            ans[x]=1;
        } else {
            vector<pii> vst;
            for (ll y: fadj[x]) {
                if (clen[y]==1) {
                    vst.push_back({clin[y].size(),y});
                }
            }
            sort(vst.begin(),vst.end());
            ll K = vst.size();
            for (ll k=0;k<(K-1);k++) {
                ll yc = vst[k].second; ll zc = vst[k+1].second;
                for (ll c0: clin[yc]) {
                    if (clin[zc].find(c0)==clin[zc].end()) {
                        ans[x]=0;
                        return;
                    }
                }
            }
            ll yc = vst[K-1].second; ll zc = x;
            for (ll c0: clin[yc]) {
                if (clin[zc].find(c0)==clin[zc].end()) {
                    ans[x]=0;
                    return;
                }
            }
            ans[x]=1;
            return;
        }
    } else {
        ll y2 = -1;
        for (ll y: fadj[x]) {
            if (clen[y]==2) {
                y2 = y;
            }
        }
        assert(y2!=-1);
        if (col2[y2]!=C[y2]) {
            ans[x]=0;
            return;
        }
        col2[x]=col2[y2];
        lbot[x]=lbot[y2];
        for (ll c0: clin[y2]) {
            if (clin[x].find(c0)==clin[x].end()) {
                ans[x]=0;
                return;
            }
        }
        if (n1in==1) {
            ans[x]=1;
            return;
        }
        vector<pii> vst;
        for (ll y: fadj[x]) {
            if (clen[y]==1) {
                vst.push_back({clin[y].size(),y});
            }
        }
        sort(vst.begin(),vst.end());
        ll K = vst.size();
        for (ll k=0;k<(K-1);k++) {
            ll yc = vst[k].second; ll zc = vst[k+1].second;
            for (ll c0: clin[yc]) {
                if (clin[zc].find(c0)==clin[zc].end()) {
                    ans[x]=0;
                    return;
                }
            }
        }
        ll yc = vst[K-1].second; ll zc = lbot[x];
        for (ll c0: clin[yc]) {
            if (clin[zc].find(c0)==clin[zc].end()) {
                ans[x]=0;
                return;
            }
        }
        ans[x]=1;
    }
}

vector<int> beechtree(int _N, int _M, vector<int> _P, vector<int> _C) {
    N=_N; M=_M;
    for (ll x=0;x<N;x++) {
        radj.push_back(_P[x]);
        if (x!=0) {
            fadj[_P[x]].push_back(x);
        }
    }
    for (ll x: _C) {
        C.push_back(x);
    }
    dfs(0);
    vector<int> vans;
    for (ll x=0;x<N;x++) {
        vans.push_back(ans[x]);
    }
    return vans;
}

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