Submission #1132854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132854		SpyrosAliv	Beech Tree (IOI23_beechtree)	C++20	14 / 100	47 ms	16712 KiB

beechtree

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

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

vector<int> solve_line() {
    vector<int> ans(n, false);
    ans[n-1] = true;
    for (int i = n-1; i >= 1; i--) {
        if (c[i] != c[n-1]) {
            break;
        }
        ans[i-1] = true;
    }
    return ans;
}

vector<int> sub;

void dfs(int node) {
    for (auto next: tree[node]) {
        if (next != p[node]) {
            dfs(next);
            sub.push_back(next);
        }
    }
}

vector<int> brute() {
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        sub.clear();
        dfs(i);
        bool f = false;
        int sz = sub.size()+1;
        sort(sub.begin(), sub.end());
        do {
            vector<int> perm, cnt(m+1, 0);
            perm.push_back(i);
            for (auto x: sub) perm.push_back(x);
            bool x =true;
            for (int j = 1; j < sz; j++) {
                if (perm[cnt[c[perm[j]]]] != p[perm[j]]) {
                    x = false;
                    break;
                }
                cnt[c[perm[j]]]++;
            }
            if (x) {
                f = true;
                break;
            }
        } while (next_permutation(sub.begin(), sub.end()) || f);
        ans[i] = f;
    }
    return ans;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N;
    m = M;
    c = C;
    p = P;
    tree.clear();
    tree.resize(n);
    bool line = true;
    for (int i = 1; i < n; i++) {
        tree[P[i]].push_back(i);
        if (P[i] != i-1) line = false;
    }
    if (line) return solve_line();
    if (n <= 8) return brute();
    vector<int> ans(n, 0);
    vector<int> dep(n, 0);
    for (int i = 1; i < n; i++) {
        if (P[i] == 0) dep[i] = 1;
        else {
            dep[i] = 2;
            ans[i] = 1;
        }
    }
    vector<int> cnt(m+1, 0);
    vector<pair<int, vector<int>>> comps;

    for (int i = 1; i < n; i++) {
        if (dep[i] != 1) continue;
        vector<int> colors;
        for (auto next: tree[i]) {
            if (next == 0) continue;
            colors.push_back(c[next]);
            cnt[c[next]]++;
        }
        sort(colors.begin(), colors.end());
        int sz = colors.size();
        comps.push_back({sz, colors});
        bool curr = true;
        for (int j = 1; j < sz; j++) {
            if (colors[j] == colors[j-1]) {
                curr = false;
                break;
            }
        }
        if (curr) ans[i] = true;
    }

    vector<bool> seen(m+1, false);
    for (int i = 0; i < n; i++) {
        if (P[i] == 0) {
            if (seen[c[i]]) return ans;
            seen[c[i]] = true;
        }
        if (i != 0 && ans[i] == 0) return ans;
    }
    for (int i = 0; i <= m; i++) {
        if (!seen[i] && cnt[i]) return ans;
    }

    if (comps.size() > 0) {
        sort(comps.rbegin(), comps.rend());
        seen.assign(m+1, false);
        int sz = comps.size();
        for (auto x: comps[0].second) seen[x] = true;
        for (int i = 1; i < sz; i++) {
            for (auto x: comps[i].second) {
                if (!seen[x]) return ans;
            }
        }
    }
    
    ans[0] = 1;
    return ans;
}
/*
int main() {
    vector<int> f = beechtree(5, 4, {-1, 0, 1, 2, 3, 4}, {0, 0, 1, 1, 1, 1});
    for (auto x: f) cout << x << " ";
    cout << '\n';
}*/

• 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