Submission #1026906

#TimeUsernameProblemLanguageResultExecution timeMemory
1026906harzuqiBosses (BOI16_bosses)C++14
100 / 100
421 ms808 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int X = 5e3 + 5;

int n, total, vis[X], d[X];
set<int> pernah;
vector<int> adj[X];

int cek(int x) {
    memset(vis, 0, sizeof vis);
    memset(d, -1, sizeof d);
    queue<int> q;
    vis[x] = 1;
    d[x] = 1;
    q.push(x);
    while(q.size()) {
        int cur = q.front();
        q.pop();
        for(int nxt: adj[cur]) {
            if(vis[nxt]) continue;
            vis[nxt] = 1;
            d[nxt] = d[cur] + 1;
            q.push(nxt);
        }
    }
    int ret = 0;
    for(int i = 1; i <= n; i++) {
        if(d[i] == -1) {
            return -1;
        } else {
            ret += d[i];
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int t, x;
        cin >> t;
        while(t--) {
            cin >> x;
            adj[x].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i = 1; i <= n; i++) {
        int cur = cek(i);
        if(cur != -1) {
            ans = min(ans, cur);
        }
    }
    cout << ans << endl;

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