제출 #1306755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306755		zbyszko	Bosses (BOI16_bosses)	C++20	100 / 100	466 ms	720 KiB

bosses

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

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