Submission #1306755

#TimeUsernameProblemLanguageResultExecution timeMemory
1306755zbyszkoBosses (BOI16_bosses)C++20
100 / 100
466 ms720 KiB
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using pii = pair<int,int>;
#define x first
#define y second

vector<vector<int>> adj;
int n;

ll bdfs(int f){
    vector<bool> visit(n+1,false);
    int used=0;
    queue<pii> q;
    q.push({f,1});
    visit[f]=true;
    used++;
    int v;
    ll sum=0;
    while(!q.empty()){
        pii p=q.front();
        q.pop();
        v=p.x;
        sum=sum+p.y;
        for(int c:adj[v]){
            if(!visit[c]){
                visit[c]=true;
                used++;
                q.push({c,p.y+1});
            }
        }
    }
    if(used<n){
        return LLONG_MAX;
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    adj.resize(n+1);
    for(int i=1,k;i<=n;i++){
        cin >> k;
        for(int j=0,v;j<k;j++){
            cin >> v;
            adj[v].push_back(i);
        }
    }
    ll sum=LLONG_MAX;
    for(int i=1;i<=n;i++){
        sum=min(sum,bdfs(i));
    } 
    cout << sum;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...