Submission #1129740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129740		MMihalev	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2095 ms	17476 KiB

beechtree

#include "beechtree.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
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 cmp(pair<int,int> i1,pair<int,int> i2)
{
    int s1=g[i1.first].size();
    int s2=g[i2.first].size();

    return s1>s2;
}
int seq[MAX_N];
int cnt[MAX_N];
int sz;
bool check(int u)
{
    if(sz>0)
    {
        if(seq[cnt[col[u]]]!=par[u])return 0;
        cnt[col[u]]++;
    }
    seq[sz++]=u;
    return 1;
}
bool solve(int r)
{
    sz=0;
    for(int i=1;i<=m;i++)cnt[i]=0;

    vector<int>q;
    q.push_back(r);

    while(q.size())
    {
        vector<int>nq;

        int Szq=q.size();
        int pos=0;

        while(Szq>0)
        {
            int u=q[pos];
            pos++;
            Szq--;

            if(check(u)==0)return 0;

            for(auto [v,edge]:g[u])
            {
                nq.push_back(v);
            }
        }
        swap(q,nq);
    }

    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++)
    {
        sort(g[i].begin(),g[i].end(),cmp);
    }

    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