Submission #1309964

#TimeUsernameProblemLanguageResultExecution timeMemory
1309964NagerhideBosses (BOI16_bosses)C++20
100 / 100
523 ms712 KiB
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> GRAF;
vector<bool> Vis;
int N;

long long TestCase(int I){
    long long Answer = 0;
    for(int i= 1; i <= N; ++i){
        Vis[i]=false;
    }
    queue<pair<int, int>> Q;
    Q.push({I, 1});
    Vis[I]=true;
    while(!Q.empty()){
        auto A = Q.front();
        Q.pop();
        Answer+=A.second;
        for(auto B : GRAF[A.first]){
            if(!Vis[B]){
                Vis[B]=true;
                Q.push({B, A.second+1});
            }
        }
    }
    for(int i = 1; i <= N; ++i){
        if(!Vis[i]){
            return 1000000000;
        }
    }
    return Answer;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    GRAF.resize(N+1);
    Vis.resize(N+1);
    for(int i = 1; i <= N; ++i){
        int K; cin >> K;
        while(K--){
            int A; cin >> A;
            GRAF[A].push_back(i);
        }
    }   
    long long BEST = 1000000000; 
    for(int i = 1; i <= N; ++i){
        BEST = min(BEST, TestCase(i));
    }
    cout << BEST;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...