Submission #1364551

#TimeUsernameProblemLanguageResultExecution timeMemory
1364551madamadam3Bosses (BOI16_bosses)C++20
100 / 100
345 ms776 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int

/*
how to assign salary:
(1) all leaves = 1
(2) every non-leaf = Σchildren + 1

= Σdepth+1 for each node

minimise total depth of the tree
= minimise shortest paths
*/

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;
    vector<vector<int>> G(n); for (int i = 0; i < n; i++) {
        int k; cin >> k;
        while (k--) {
            int j; cin >> j;
            G[j-1].push_back(i);
        }
    }

    int ans = 4e18;
    for (int i = 0; i < n; i++) {
        queue<int> q; q.push(i);
        vector<int> dist(n, -1); dist[i] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto v : G[u]) {
                if (dist[v] == -1 || dist[u] + 1 < dist[v]) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        if (*min_element(dist.begin(), dist.end()) == -1) continue;
        ans = min(ans, accumulate(dist.begin(), dist.end(), n));
    }
    cout << ans << "\n";

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...