제출 #1058055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058055		Ignut	참나무 (IOI23_beechtree)	C++17	9 / 100	34 ms	11860 KiB

beechtree

/* Ignut
started: 14.08.2024
now: 14.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;
int n;

vector<int> tree[MAXN];
vector<int> p;
vector<int> c;

vector<int> res;

int cnt[MAXN] = {};

bool Check(vector<int> &lst, int root) {
    // if (root == 4) {
    //     cout << root << " :\n";
    // }
    sort(lst.begin(), lst.end());
    do {
        bool ok = true;
        for (int v : lst) {
            int par = cnt[c[v]];
            int vert = (par == 0 ? root : lst[par - 1]);
            // if (root == 4) {
            //     cout << v << " -> " << par << ", ";
            // }
            if (p[v] != vert) {
                ok = false; break;
            }
            cnt[c[v]] ++;
        }
        // if (root == 4) {
        //     cout << '\n';
        // }
        for (int v : lst) cnt[c[v]] = 0;
        if (ok) return true;
    } while (next_permutation(lst.begin(), lst.end()));
    return false;
}

vector<int> dfs(int v) {
    vector<int> lst = {};
    for (int to : tree[v])
        if (to != p[v])
            for (int u : dfs(to))
                lst.push_back(u);
    res[v] |= Check(lst, v);
    lst.push_back(v);
    return lst;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N; p = P; c = C;
    res.assign(N, 0);
    if (N <= 8) {
        // cout << "brute\n";
        for (int i = 1; i < N; i ++) {
            tree[i].push_back(P[i]);
            tree[P[i]].push_back(i);
        }
        dfs(0);
        return res;
    }
    int cnt = 0;
    for (int i = 1; i < N; i ++) cnt += (P[i] != 0);
    if (cnt <= 1) res[0] = 1;
    for (int i = 1; i < N; i ++) res[i] = 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