제출 #1345950

#제출 시각아이디문제언어결과실행 시간메모리
1345950killerzaluuBosses (BOI16_bosses)C++20
100 / 100
328 ms736 KiB
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> rev(n + 1);

    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            rev[x].push_back(i);
        }
    }

    const long long INF = (long long)4e18;
    long long ans = INF;

    for (int root = 1; root <= n; root++) {
        vector<int> dist(n + 1, -1);
        queue<int> q;

        dist[root] = 0;
        q.push(root);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : rev[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }

        long long cur = n;
        bool ok = true;

        for (int i = 1; i <= n; i++) {
            if (dist[i] == -1) {
                ok = false;
                break;
            }
            cur += dist[i];
        }

        if (ok) ans = min(ans, cur);
    }

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