Submission #1281121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281121		Luvidi	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2099 ms	74884 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5;
vector<int> cc[maxn],ch[maxn],ans,c,p;

bool fd(int x,int v){
    auto it=lower_bound(cc[v].begin(),cc[v].end(),x);
    return it!=cc[v].end()&&(*it)==x;
}

vector<int> dfs(int v){
    vector<int> s={};
    if(!cc[v].empty())s.push_back(v);
    for(int u:ch[v]){
        auto t=dfs(u);
        for(int i:t)s.push_back(i);
        ans[v]&=ans[u];
    }
    sort(s.begin(),s.end(),[&](int x,int y){return cc[x].size()>cc[y].size();});
    for(int i=0;i+1<s.size();i++){
        for(int j:cc[s[i+1]])ans[v]&=fd(j,s[i]);
    }
    map<int,int> ce;
    for(int i=1;i<s.size();i++){
        ans[v]&=p[s[i]]==s[ce[c[s[i]]]++];
    }
    return s;
}

std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{   
    p=P;
    c=C;
    for(int i=1;i<n;i++){
        cc[p[i]].push_back(c[i]);
        ch[p[i]].push_back(i);
    }
    ans=vector<int>(n,1);
    for(int v=0;v<n;v++){
        sort(cc[v].begin(),cc[v].end());
        for(int i=0;i+1<cc[v].size();i++)ans[v]&=cc[v][i]!=cc[v][i+1];
    }
    dfs(0);
    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