Submission #955943

#	Time	Username	Problem	Language	Result	Execution time	Memory
955943		Dan4Life	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2062 ms	9500 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

const int mxN = (int)2000;
int n, m;
vector<int> ans, col, par, adj[mxN];
vector<int> sub[mxN];

void dfs(int s, int p){
    sub[s].pb(s);
    for(auto u : adj[s]){
        if(u==p) continue;
        dfs(u,s);
        for(auto child : sub[u]) 
            sub[s].pb(child);
    }
    if(sz(sub[s])==1) ans[s] = 1;
    sort(all(sub[s]));
    do{
        bool ok = 1; if(sub[s][0]!=s) continue;
        for(int i = 1; i < sz(sub[s]); i++){
            int f = 0, node = sub[s][i];
            int cur_col = col[node];
            for(int j = 1; j < i; j++){
                int nodej = sub[s][j];
                int chk_col = col[nodej];
                if(chk_col==cur_col) f++;
            }
            if(par[node]!=sub[s][f]) ok = 0;
        }
        if(ok) ans[s]=1;
    }while(next_permutation(all(sub[s])));
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
    n = N, m = M;
    ans.clear(); col.clear(); par.clear();
    for(int i = 0; i < N; i++) 
        sub[i].clear(), adj[i].clear();

    for(int i = 0; i < N; i++) ans.pb(0);
    for(auto u : C) col.pb(u);
    for(auto u : P) par.pb(u);
    for(int i = 1; i < N; i++){
        adj[P[i]].pb(i);
        adj[i].pb(P[i]);
    }
    dfs(0,-1); 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