Submission #340724

#TimeUsernameProblemLanguageResultExecution timeMemory
340724bigDuckBosses (BOI16_bosses)C++14
100 / 100
831 ms876 KiB
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


int t, n, m, k, a[300010], q, l, r;

vector<int> g[5010];
bool v[5010];




int bfs(int s){
int sum=1;
queue<pii> q;
q.push({s, 1});
v[s]=true;

while(!q.empty()){
    pii pr=q.front(); q.pop();
    int node=pr.ft, d=pr.sc;
    for(int u:g[node]){
        if(!v[u]){
            q.push({u, d+1});
            sum+=d+1;
            v[u]=true;
        }
    }
}
for(int i=1; i<=n; i++){
    if(v[i]==false){
        sum=1e9;
    }
    v[i]=false;
}
return sum;
}




int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>k;
    for(int j=1; j<=k; j++){
        int v; cin>>v;
        g[v].pb(i);
    }
}


int res=1e9;
for(int i=1; i<=n; i++){
    res=min(res, bfs(i));
}
cout<<res;



return 0;
}



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