Submission #1350944

#TimeUsernameProblemLanguageResultExecution timeMemory
1350944msab3fBosses (BOI16_bosses)C++20
100 / 100
326 ms708 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5000 + 10;

int n, m, dist[MAX_N];
vector<int> adj[MAX_N];
long long ans;

int main() {
    cin >> n;

    for (int u = 1; u <= n; ++u) {
        int k;
        cin >> k;
        while (k--) {
            int v;
            cin >> v;
            adj[v].push_back(u);
        }
    }

    ans = 1e18;

    for (int r = 1; r <= n; ++r) {
        fill(dist + 1, dist + n + 1, 0);
        queue<int> q;
        q.push(r);
        dist[r] = 1;
        int rem = n;
        long long sum = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            --rem, sum += dist[u];
            for (int v : adj[u])
                if (dist[v] == 0) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
        }
        if (rem == 0) ans = min(ans, sum);
    }

    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...