Submission #1232722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232722		antonn	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2095 ms	51268 KiB

beechtree

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

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, m;
vector<int> g[N];
int col[N], ok[N], par[N];

bool check(int u, vector<pair<int, int>> v) {
    sort(v.begin(), v.end());
    do {
        bool ok = 1;
        if (v[0].first != u) ok = 0; 
        
        vector<int> cnt(m + 1, 0);
        for (int i = 1; i < v.size(); ++i) {
            int f = cnt[v[i].second];
            ok &= v[f].first == par[v[i].first];
            cnt[v[i].second]++;
        }
    
        if (ok) return true;
    } while (next_permutation(v.begin(), v.end()));
    return false;
}

vector<pair<int, int>> dfs(int u) {
    vector<pair<int, int>> sub;
    sub.push_back({u, col[u]});
    for (auto v : g[u]) {
        vector<pair<int, int>> children = dfs(v);
        for (auto x : children) sub.push_back(x); 
    }
    if (check(u, sub)) {
        ok[u] = 1;
    }
    return sub;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N;
    m = M;
    for (int i = 0; i < n; ++i) {
        par[i] = P[i];
        if (i > 0) {
            g[P[i]].push_back(i);
        }
    }
    for (int i = 0; i < n; ++i) {
        col[i] = C[i];
    }
    dfs(0);
    vector<int> ret(n);
    for (int i = 0; i < n; ++i) ret[i] = ok[i];
    return ret; 
}

• 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