Submission #1327626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327626		SpyrosAliv	Beech Tree (IOI23_beechtree)	C++20	0 / 100	0 ms	400 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> p, c;
vector<vector<int>> tree;

bool superset(set<int> A, set<int> B) {
    for (auto x: B) {
        if (A.find(x) == A.end()) return false;
    }
    return true;
}

vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    n = N;
    m = M;
    p = P;
    c = C;
    for (int i = 1; i < n; i++) {
        tree[p[i]].push_back(i);
    }
    vector<int> ans(n, 0);
    vector<set<int>> cols(n);
    for (int i = 1; i < n; i++) {
        if (tree[i].size() == 0) {
            ans[i] = 1;
            continue;
        }
        for (auto next: tree[i]) {
            cols[i].insert(c[next]);
        }
        if (cols[i].size() != tree[i].size()) {
            ans[i] = 0;
        }
        else ans[i] = 1;
    }
    for (auto next: tree[0]) {
        cols[0].insert(c[next]);
    }
    if (cols[0].size() != tree[0].size()) {
        ans[0] = 0;
        return ans;
    }
    vector<pair<int, set<int>>> cands;
    for (auto next: tree[0]) {
        cands.push_back({cols[next].size(), cols[next]});
    }
    sort(cands.rbegin(), cands.rend());
    set<int> curr = cols[0];
    for (auto [sz, nxt]: cands) {
        if (!superset(curr, nxt)) {
            ans[0] = 0;
            return ans;
        }
        curr = nxt;
    }
    ans[0] = 1;
    return ans;
}

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