Submission #1235134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235134		guagua0407	Beech Tree (IOI23_beechtree)	C++20	100 / 100	569 ms	151980 KiB

beechtree

#include "beechtree.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

namespace{
    const int mxn=2e5+5;
}

std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> c)
{
    vector<vector<int>> adj(n);
    for(int i=1;i<n;i++){
        adj[P[i]].push_back(i);
    }
    vector<int> ans(n,1);
    vector<map<int,int>> mp(n);
    for(int v=0;v<n;v++){
        for(auto u:adj[v]){
            mp[v][c[u]]=u;
        }
        if((int)adj[v].size()!=(int)mp[v].size()) ans[v]=0;
    }
    vector<int> sz(n);
    function<void(int)> dfs0=[&](int v){
        sz[v]=1;
        for(auto u:adj[v]){
            dfs0(u);
            sz[v]+=sz[u];
        }
    };
    dfs0(0);
    vector<set<pair<pair<int,int>,int>>> S(n);
    int cur;
    function<bool(int,int)> subset=[&](int a,int b){
        //cout<<cur<<' '<<a<<' '<<b<<'\n';
        if((int)adj[a].size()==(int)adj[b].size()){
            if(sz[a]<sz[b]) return subset(b,a);
        }
        for(auto u:mp[b]){
            if(mp[a].find(u.f)==mp[a].end() or sz[mp[a][u.f]]<sz[u.s]) return false;
        }
        return true;
    };
    function<void(int)> dfs=[&](int v){
        S[v].insert({{(int)adj[v].size(),sz[v]},v});
        for(auto u:adj[v]){
            dfs(u);
            ans[v]&=ans[u];
            cur=v;
            if((int)S[v].size()<(int)S[u].size()) swap(S[v],S[u]);
            for(auto x:S[u]){
                auto it=S[v].lower_bound(make_pair(x.f,0));
                if(it!=S[v].end()) ans[v]&=subset((*it).s,x.s);
                if(!S[v].empty() and it!=S[v].begin()) ans[v]&=subset(x.s,(*prev(it)).s);
                S[v].insert(x);
            }
        }
    };
    dfs(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