Submission #955859

#	Time	Username	Problem	Language	Result	Execution time	Memory
955859		Dan4Life	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2019 ms	348 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)20;
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);
    }
    vector<int> v(sz(sub[s]),0); iota(all(v),0);
    do{
        bool ok = 1; if(v[0]!=0) continue;
        for(int i = 0; i < sz(v); i++){
            int f = 0, node = sub[s][v[i]];
            int cur_col = col[node];
            for(int j = 0; j < i; j++){
                int nodej = sub[s][v[j]];
                int chk_col = col[nodej];
                if(chk_col==cur_col) f++;
            }
            if(i and par[node]!=sub[s][v[f]]) ok = 0;
        }
        if(ok) { ans[s] = 1; break; }
    }while(next_permutation(all(v)));
}

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

    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: 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