Submission #1066705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066705		LittleOrange	Beech Tree (IOI23_beechtree)	C++17	0 / 100	1 ms	348 KiB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    ll n = N;
    ll m = M;
    vector<vector<ll>> ch(n);
    for(ll i = 1;i<n;i++) ch[P[i]].push_back(i);
    vector<ll> ord;
    {
        function<void(ll)> dfs;
        dfs = [&](ll i){
            ord.push_back(i);
            for(ll j : ch[i]) dfs(j);
        };
        dfs(0);
    }
    vector<ll> rord = ord;
    reverse(rord.begin(),rord.end());
    vector<ll> bad(n,0);
    for(ll i : rord){
        vector<ll> v;
        for(ll j : ch[i]){
            if (bad[j]) bad[i] = 1;
            v.push_back(C[j]);
            if(ch[i].size()<ch[j].size()) bad[i] = 1;
        }
        sort(v.begin(),v.end());
        if (unique(v.begin(),v.end())!=v.end()) bad[i] = 1;
    }
    vector<ll> ans(n);
    for(ll i = 0;i<n;i++) ans[i] = !bad[i];
    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:8:8: warning: unused variable 'm' [-Wunused-variable]
    8 |     ll m = M;
      |        ^

• 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