Submission #1309964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309964		Nagerhide	Bosses (BOI16_bosses)	C++20	100 / 100	523 ms	712 KiB

bosses

#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;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33