Submission #1131011

#TimeUsernameProblemLanguageResultExecution timeMemory
1131011Hamed_GhaffariBosses (BOI16_bosses)C++20
100 / 100
475 ms736 KiB
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

#define pb push_back

const int MXN=5001;

int n;
vector<int> g[MXN];
int dis[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        int k;
        cin >> k;
        for(int j=0; j<k; j++) {
            int v;
            cin >> v;
            g[v].pb(i);
        }
    }
    int ans=1e9;
    for(int i=1; i<=n; i++) {
        fill(dis+1, dis+n+1, -1);
        dis[i] = 1;
        int cur=1;
        queue<int> q;
        q.push(i);
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            for(int u : g[v])
                if(dis[u]==-1) {
                    cur += (dis[u]=dis[v]+1);
                    q.push(u);
                }
        }
        if(*min_element(dis+1, dis+n+1) != -1) 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...