Submission #1129766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129766		MMihalev	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2098 ms	43576 KiB

beechtree

#include "beechtree.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
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];

int level[MAX_N];
vector<int>nodes;
vector<int>nodescol[MAX_N];
void dfs(int u)
{
    for(auto [v,edge]:g[u])
    {
        nodescol[edge].push_back(v);
        nodes.push_back(v);
        dfs(v);
    }
}
bool solve(int r)
{
    nodes.clear();
    for(int i=0;i<n;i++)level[i]=1e9;
    for(int i=1;i<=m;i++)nodescol[i].clear();

    dfs(r);

    if(nodes.size()==0)return 1;

    vector<pair<int,int>>colcnt;

    for(int i=1;i<=m;i++)
    {
        if(nodescol[i].size()==0)continue;
        colcnt.push_back({(int)nodescol[i].size(),i});
    }

    sort(colcnt.rbegin(),colcnt.rend());

    set<int>s;
    bool start=0;

    for(auto [prefixsz,curcol]:colcnt)
    {
        prefixsz--;

        if(start==0)
        {
            for(int v:nodescol[curcol])
            {
                if(s.count(par[v]))return 0;
                level[par[v]]=prefixsz;
                s.insert(par[v]);
            }
            start=1;
            continue;
        }

        set<int>ns;

        for(int v:nodescol[curcol])
        {
            if(s.count(par[v])==0)return 0;

            if(ns.count(par[v]))return 0;
            level[par[v]]=prefixsz;
            ns.insert(par[v]);
        }

        swap(ns,s);
    }

    for(auto v:nodes)
    {
        if(level[v]<level[par[v]])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++)
    {
        ans[i]=solve(i);
    }

    return ans;
}

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