Submission #1230326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230326		vladilius	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2092 ms	34824 KiB

beechtree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c){
    vector<int> g[n], d(n);
    for (int i = 1; i < n; i++){
        g[p[i]].pb(i);
        d[i] = d[p[i]] + 1;
    }
    
    vector<int> f(n);
    for (int i = 0; i < n; i++) f[i] = (int) g[i].size();
    
    vector<int> h;
    function<void(int)> dfs = [&](int v){
        h.pb(v);
        for (int i: g[v]){
            dfs(i);
        }
    };

    vector<int> out;
    for (int i = 0; i < n; i++){
        h.clear();
        dfs(i);
        
        vector<arr3> all;
        for (int j: h){
            all.pb({d[j], -f[j], j});
        }
        
        sort(all.begin(), all.end());
        vector<int> o;
        for (auto p: all) o.pb(p[2]);
        
        vector<int> cc(m + 1);
        bool I = 1;
        for (int j = 1; j < o.size(); j++){
            if (o[cc[c[o[j]]]] != p[o[j]]){
                I = 0;
                break;
            }
            cc[c[o[j]]]++;
        }
        
        out.pb(I);
    }
    
    return out;
}

• 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