제출 #1343254

#제출 시각아이디문제언어결과실행 시간메모리
1343254PakinDioxideBosses (BOI16_bosses)C++17
100 / 100
1429 ms12628 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 5e5+5;

int n, mn = INT_MAX;
vector <int> adj[mxN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int c; cin >> c;
        for (int j = 0, x; j < c; j++) cin >> x, adj[x].emplace_back(i);
    }
    for (int i = 1; i <= n; i++) {
        int vis[n+1]; memset(vis, 0, sizeof(vis));
        vector <int> adt[n+1];
        queue <int> q;
        q.emplace(i);
        while (q.size()) {
            int u = q.front(); q.pop();
            vis[u] = 1;
            for (auto v : adj[u]) if (!vis[v]) q.emplace(v), vis[v] = 1, adt[u].emplace_back(v);
        }
        int cnt = 0, cc = 0;
        function <int(int)> dfs = [&] (int u) {
            int sz = 1;
            cc++;
            for (auto v : adt[u]) sz += dfs(v);
            cnt += sz;
            return sz;
        };
        dfs(i);
        if (cc == n) mn = min(mn, cnt);
    }
    cout << mn << '\n';
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...