Submission #1308658

#TimeUsernameProblemLanguageResultExecution timeMemory
1308658miku_Bosses (BOI16_bosses)C++20
100 / 100
549 ms740 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
const int s = 5005;
vector<int>v[s];
int lvl[s];
queue<pii>kol;
void bfs(int node){
    kol.push({node, 1});
    while(kol.size()){
        if(lvl[kol.front().first] != 0){
            kol.pop();
            continue;
        }
        lvl[kol.front().first] = kol.front().second; 
        for (int i: v[kol.front().first]){
            if(lvl[i] == 0) kol.push({i, lvl[kol.front().first] + 1});
        }
    }
}
void f(){
    int n, ans = s * s; cin >> n;
    for(int i = 1; i <= n; i++){
        int k; cin >> k;
        for(int j = 0; j < k; j++){
            int x; cin >> x;
            v[x].pb(i);
        }
    }
    for(int i = 1; i <= n; i++){
        int curr = 0;
        for(int j = 1; j <= n; j++) lvl[j] = 0;
        bfs(i);
        for(int j = 1; j <= n; j++){
            if(lvl[j] == 0) curr = s * s;
            curr += lvl[j];
        } 
        ans = min(ans, curr);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    f();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...