Submission #1205009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205009		PagodePaiva	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2095 ms	12220 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

vector <int> g[N];
vector <int> componentes[N];
int cor[N];
int cnt[N];
int perm[N];
int pai[N];
vector <int> cores;
int res[N];

void dfs(int v, int p){
    pai[v] = p;
    res[v] = 0;
    componentes[v].push_back(v);
    for(auto x : g[v]){
        if(x == p)
            continue;
        dfs(x, v);
        for(auto val : componentes[x])
            componentes[v].push_back(val);
    }
    sort(componentes[v].begin(), componentes[v].end());
    do{
        if(v != componentes[v][0])
            continue;
        for(int i = 0;i < componentes[v].size();i++){
            perm[componentes[v][i]] = i;
        }
        bool aux = true;
        for(int i = 1;i < componentes[v].size();i++){
            if(perm[pai[componentes[v][i]]] != cnt[cor[componentes[v][i]]]){
                aux = false;
            }
            cnt[cor[componentes[v][i]]]++;
        }
        if(aux)
            res[v] = true;
        for(auto x : cores)
            cnt[x] = 0;
    } while(next_permutation(componentes[v].begin(), componentes[v].end()));
    return;
}

vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c){
    for(int i = 1;i < n;i++){
        g[i].push_back(p[i]);
        g[p[i]].push_back(i);
        cor[i] = c[i];
        cores.push_back(c[i]);
    }
    dfs(0, 0);
    vector <int> ans;
    for(int i = 0;i < n;i++)
        ans.push_back(res[i]);
    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