Submission #1130784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130784		MMihalev	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2101 ms	154440 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,m;
vector<pair<int,int>>g[MAX_N];
int par[MAX_N];
int col[MAX_N];
bool good[MAX_N];
void dfsgood(int u)
{
    set<int>s;
    for(auto [v,edge]:g[u])
    {
        if(s.count(edge))good[u]=0;
        s.insert(edge);
        dfsgood(v);
        good[u]=min(good[u],good[v]);
    }
}
vector<int>nodes;
set<int>typesset;
int types;
int curtype;
int type[MAX_N];
int cnt[MAX_N][100];
void dfsnode(int u)
{
    nodes.push_back(u);
    typesset.insert((int)g[u].size());

    for(auto [v,edge]:g[u])
    {
        dfsnode(v);
    }
}
void dfs(int u,int ty)
{
    if(g[u].size()==curtype)
    {
        type[u]=ty;
        cnt[u][ty]=1;
    }
    else cnt[u][ty]=0;

    for(auto [v,edge]:g[u])
    {
        dfs(v,ty);
        cnt[u][ty]+=cnt[v][ty];
    }
}
int seq[MAX_N];
int sz;
map<int,int>cntt;
int root;
bool add(int u)
{
    if(sz==0)
    {
        if(u!=root)return 0;
    }
    else
    {
        if(seq[cntt[col[u]]]!=par[u])return 0;
        cntt[col[u]]++;
    }
    seq[sz++]=u;
    return 1;
}
bool cmp(int x,int y)
{
    return cnt[x][curtype]<cnt[y][curtype];
}
bool cmp2(int x,int y)
{
    return seq[par[x]]<seq[par[y]];
}
bool solve(int r)
{
    if(good[r]==0)return 0;

    root=r;
    types=0;
    typesset.clear();
    nodes.clear();
    cntt.clear();
    sz=0;

    dfsnode(r);

    if(nodes.size()<=2)return 1;

    for(int u:nodes)type[u]=-1;

    for(int downedges:typesset)
    {
        curtype=downedges;
        dfs(r,types);
        types++;
    }

    vector<vector<int>>v;
    v.push_back(nodes);

    for(int ty=types-1;ty>=0;ty--)
    {
        curtype=ty;
        vector<vector<int>>nv;
        vector<int>vv;

        for(auto&curblock:v)
        {
            sort(curblock.rbegin(),curblock.rend(),cmp);

            int prev=-1;
            for(auto&x:curblock)
            {
                if(cnt[x][ty]!=prev)
                {
                    if(prev!=-1)nv.push_back(vv);
                    vv.clear();
                }
                vv.push_back(x);
                prev=cnt[x][ty];
            }
            nv.push_back(vv);
        }

        swap(nv,v);
    }


    for(auto&curblock:v)
    {
        sort(curblock.begin(),curblock.end(),cmp2);
        for(auto&x:curblock)
        {
            if(add(x)==0)return 0;
        }
    }

    return 1;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n=N;
    m=M;

    vector<int>ans;
    ans.resize(n);

    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;
    }

    dfsgood(0);

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

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12