Submission #1220389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220389		trimkus	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2096 ms	71492 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    vector<int> res(N);
    vector<vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        adj[P[i]].push_back(i);
    }
    auto dfs = [&](auto& dfs, int i, int p) -> vector<int> {
        vector<int> vert;
        for (auto& u : adj[i]) {
            if (u == p) continue;
            for (auto j : dfs(dfs, u, i)) {
                vert.push_back(j);
            }
        }
        auto seq = vert;
        sort(begin(seq), end(seq));
        // cerr << i << " = ";
        // for (auto& u : seq) {
        //     cerr << u << " ";
        // }
        // cerr << "\n";
        do {
            vector<int> now = seq;
            now.insert(now.begin(), i);
            map<int, int> cnt;
            bool ok = true;
            for (auto& j : seq) {
                if (now[cnt[C[j]]] != P[j]) {
                    ok = false;
                    break;
                }
                cnt[C[j]] += 1;
            }
            if (ok) {
                res[i] = 1;
                break;
            }
        } while (next_permutation(begin(seq), end(seq)));
        vert.push_back(i);
        return vert;
    };
    dfs(dfs, 0, -1);
    return res;
}

• 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