Submission #1219904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219904		madamadam3	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2099 ms	60696 KiB

beechtree

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

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

vi par, colour, ans;
vvi adj;

bool permutation_exists(vi &perm, set<int> &avail) {
    if (avail.size() == 0) {
        bool valid = true;
        for (int i = 1; i < perm.size(); i++) {
            int fi = 0; for (int j = 1; j < i; j++) if (colour[perm[j]] == colour[perm[i]]) fi++;
            valid = valid && par[perm[i]] == perm[fi];
        }

        return valid;
    }

    set<int> new_avail = avail;
    for (auto &el : avail) {
        new_avail.erase(el);
        perm.push_back(el);

        if (permutation_exists(perm, new_avail)) return true;

        perm.pop_back();
        new_avail.insert(el);
    }
    return false;
}

void dfs(int u, int p, set<int> &st) {
    st.insert(u);

    for (int v : adj[u]) {
        if (v == p) continue;

        set<int> child_avail;
        dfs(v, u, child_avail);

        st.merge(child_avail);
    }

    vi perm = {u};
    st.erase(u);
    ans[u] = permutation_exists(perm, st) ? 1 : 0;
    st.insert(u);
}

vi beechtree(int N, int M, vi P, vi C) {
    par = P; colour = C;
    adj.assign(N, vi());
    for (int i = 1; i < N; i++) {
        adj[P[i]].push_back(i);
        adj[i].push_back(P[i]);
    }
    ans.assign(N, 1);

    set<int> avail;
    dfs(0, 0, avail);

    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