Submission #1208923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208923		ml_tss	Bosses (BOI16_bosses)	C++20	67 / 100	1578 ms	1024 KiB

bosses

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

int dfs(int u, const vector<vector<int>>& children, vector<int>& prices) {
    int total = 0;
    for (int v : children[u]) {
        total += dfs(v, children, prices);
    }
    return prices[u] = total + 1;
}

int cost(const vector<int>& parent, vector<int>& prices) {
    int n = parent.size();
    vector<vector<int>> children(n);
    int root = -1;
    for (int i = 0; i < n; ++i) {
        if (parent[i] == 0) root = i;
        else children[parent[i] - 1].push_back(i);
    }
    dfs(root, children, prices);
    return accumulate(prices.begin(), prices.end(), 0);
}

int build_tree(int root, const vector<vector<int>>& constraint, vector<int>& tree, vector<int>& prices, queue<int>& q) {
    int n = constraint.size() - 1;
    fill(tree.begin(), tree.end(), -1);
    fill(prices.begin(), prices.end(), 0);
    while (!q.empty()) q.pop();
    tree[root - 1] = 0;
    q.push(root);
    int count = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        ++count;
        for (int i : constraint[node]) {
            if (tree[i - 1] == -1) {
                tree[i - 1] = node;
                q.push(i);
            }
        }
    }
    if (count != n) return INT_MAX;
    return cost(tree, prices);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<vector<int>> constraint(N + 1);
    for (int i = 1; i <= N; ++i) {
        int c;
        cin >> c;
        while (c--) {
            int t;
            cin >> t;
            constraint[t].push_back(i);
        }
    }
    int mini = INT_MAX;
    vector<int> tree(N), prices(N);
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        int val = build_tree(i, constraint, tree, prices, q);
        if (val < mini) mini = val;
    }
    cout << mini;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33