Submission #1058487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058487		shmax	Beech Tree (IOI23_beechtree)	C++17	14 / 100	39 ms	4320 KiB

beechtree

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


using namespace std;

#define len(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 1000'000'000


template<typename T>
using vec = vector<T>;


template<typename T>
using graph = vec<vec<T>>;


std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C) {
    if (n <= 8) {
        graph<int> g(n);
        for (int i = 1; i < n; ++i) {
            g[P[i]].push_back(i);
        }

        vec<bool> good(n);

        auto check = [&](int x) -> bool {
            vec<int> v;
            function<void(int)> dfs = [&](int t) {
                v.push_back(t);
                for (int u: g[t]) {
                    dfs(u);
                }
            };
            dfs(x);
            sort(all(v));
            bool res = false;
            do {
                if (v[0] != x) continue;
                auto f = [&](int i) {
                    int clr = C[v[i]];
                    int cnt = 0;
                    for (int j = 1; j < i; j++) {
                        cnt += C[v[j]] == clr;
                    }
                    return cnt;
                };

                bool good = true;
                for (int j = 1; j < len(v); j++) {
                    if (P[v[j]] != v[f(j)]) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    res = true;
                    break;
                }
            } while (next_permutation(all(v)));
            return res;
        };
        vec<int> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = check(i);
        }
        return res;
    } else {
        vec<int> res(n);
        res[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (C[i] == C[i + 1]) {
                res[i] = true;
            } else {
                res[i] = true;
                break;
            }
        }
        return res;
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 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