Submission #1233944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233944		Muhammad_Aneeq	Beech Tree (IOI23_beechtree)	C++17	0 / 100	72 ms	52416 KiB

beechtree

#include "beechtree.h"
#include <vector>
#include <set>
using namespace std;
int const N=2e5+10;
vector<int>nei[N];
int sz[N]={};
int col[N]={},p[N];
bool ans[N]={};
void dfs(int u)
{
    sz[u]=1;
    set<int>s;
    bool w=0;
    ans[u]=1;
    for (auto i:nei[u])
    { 
        dfs(i);
        s.insert(col[i]);
        sz[u]+=sz[i];
        ans[u]=(ans[u]&ans[i]);
    }   
    ans[u]=ans[u]&(s.size()==nei[u].size());
    for (auto i:nei[u])
    {
        if (sz[i]>1)
        {
            if (w)
            {
                ans[u]=0;
                return ;
            }
            w=1;
            int g=col[i];
            bool er=0;
            for (auto j:nei[i])
            {
                if (nei[j].size())
                {
                    er=0;
                    break;
                }
                if (s.find(col[j])!=s.end())
                    er=1;
            }
            if (er==0)
            {
                ans[u]=0;
                return;
            }
        }
    }
    if (w&&u!=0)
        ans[p[u]]=0;
}
vector<int> beechtree(int N, int M, vector<int> P,vector<int> C)
{
    for (int i=1;i<N;i++)
    {
        p[i]=P[i];
        nei[P[i]].push_back(i);
        col[i]=C[i];
    }
    dfs(0);
    vector<int>an;
    for (int i=0;i<N;i++)
        an.push_back(ans[i]);
    return an;
}

• 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