Submission #1131195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131195		MMihalev	Beech Tree (IOI23_beechtree)	C++17	100 / 100	261 ms	83004 KiB

beechtree

#include "beechtree.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<tuple>
using namespace std;
const int MAX_N=2e5+5;
int n,mm;
vector<pair<int,int>>g[MAX_N];
map<int,int>coltochild[MAX_N];
int par[MAX_N];
int col[MAX_N];
bool good[MAX_N];
bool ok[MAX_N];
int sz[MAX_N];
int T;
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
void dfs0(int u)
{
    in[u]=++T;
    ver[T]=u;
    sz[u]=1;
    set<int>s;
    for(auto [v,edge]:g[u])
    {
        if(s.count(edge))good[u]=0;
        s.insert(edge);
        coltochild[u][edge]=v;
        dfs0(v);
        sz[u]+=sz[v];
        good[u]=min(good[u],good[v]);
    }
    out[u]=T;
}
bool checksmaller(int a,int b)
{
    for(auto [v,edge]:g[b])
    {
        if(coltochild[a].find(edge)==coltochild[a].end())return 0;
        if(sz[coltochild[a][edge]]<sz[v])return 0;
    }
    return 1;
}
bool checkequal(int a,int b)
{
    if(g[a].size()!=g[b].size())return 0;
    for(auto [v,edge]:g[b])
    {
        if(coltochild[a].find(edge)==coltochild[a].end())return 0;
        if(sz[coltochild[a][edge]]!=sz[v])return 0;
    }
    return 1;
}
map<int,int>m;
void add(int node,int u)
{
    if(m.find(sz[node])==m.end())
    {
        auto it=m.upper_bound(sz[node]);
        if(it!=m.end())
        {
            if(checksmaller(it->second,node)==0)ok[u]=0;
        }
        if(it!=m.begin())
        {
            it--;
            if(checksmaller(node,it->second)==0)ok[u]=0;
        }
        m[sz[node]]=node;
    }
    else
    {
        if(checkequal(m[sz[node]],node)==0)ok[u]=0;
    }
}
void dfs(int u,bool keep)
{
    ok[u]=good[u];

    int mx=-1,bigchild=-1;

    for(auto [v,edge]:g[u])
    {
        if(sz[v]>mx)
        {
            mx=sz[v];
            bigchild=v;
        }
    }

    for(auto [v,edge]:g[u])
    {
        if(v!=bigchild)
        {
            dfs(v,0);
            ok[u]=min(ok[u],ok[v]);
        }
    }

    if(bigchild!=-1)
    {
        dfs(bigchild,1);
        ok[u]=min(ok[u],ok[bigchild]);
    }

    for(auto [v,edge]:g[u])
    {
        if(v==bigchild)continue;

        for(int pos=in[v];pos<=out[v];pos++)
        {
            int node=ver[pos];

            add(node,u);
        }
    }

    add(u,u);

    if(keep==0)
    {
        m.clear();
    }
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n=N;
    mm=M;

    vector<int>ans;
    ans.resize(n);
    m.clear();
    T=0;

    for(int i=0;i<n;i++)
    {
        g[i].clear();
        coltochild[i].clear();
    }

    for(int i=1;i<n;i++)
    {
        par[i]=P[i];
        col[i]=C[i];

        g[P[i]].push_back({i,C[i]});
    }

    for(int i=0;i<n;i++)
    {
        good[i]=1;
        ok[i]=1;
    }

    dfs0(0);
    dfs(0,0);

    for(int i=0;i<n;i++)
    {
        ans[i]=ok[i];
    }

    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