Submission #1230336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230336		vladilius	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2096 ms	31200 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> help(int n, int m, vector<int> p, vector<int> c){
    vector<int> g[n];
    for (int i = 1; i < n; i++) g[p[i]].pb(i);
    
    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);
        
        if (h.size() == 1){
            out.pb(1);
            continue;
        }
        
        int tt = 1;
        vector<int> P;
        for (int j = 1; j < h.size(); j++){
            tt *= j;
            P.pb(j);
        }
        
        bool II = 0;
        while (tt--){
            vector<int> o = {i};
            for (int j = 0; j < P.size(); j++){
                o.pb(h[P[j]]);
            }
            
            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]]]++;
            }
            
            if (I){
                II = 1;
                break;
            }
            
            next_permutation(P.begin() + 1, P.end());
        }
        
        out.pb(II);
    }
    return out;
}

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c){
    return help(n, m, p, 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;
    }
    
    p[0] = 0;
    
    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[p[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