제출 #1167282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167282		ocasu	Bosses (BOI16_bosses)	C++20	100 / 100	609 ms	820 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf=5e18;

signed main(){
    int n; cin>>n;
    vector<vector<int>> adj(n+1);
    for (int i=1; i<=n; i++){
        int k; cin>>k;
        for (int j=0; j<k; j++){
            int x; cin>>x;
            adj[x].push_back(i);
        }
    }
    int ans=inf;
    for (int r=1; r<=n; r++){
        vector<int> d(n+1,-1);
        vector<int> numInLayer(n+1,0);
        queue<pair<int,int>> q;
        q.push({r,0});
        int numVis=0;
        while (!q.empty()){
            auto [node,dist]=q.front(); q.pop();
            if (d[node]!=-1) continue;
            d[node]=dist;
            numInLayer[dist]++;
            numVis++;
            for (auto i: adj[node]) q.push({i,dist+1});
        }
        if (numVis<n) continue;
        int sum=0;
        for (int i=n-1; i>=0; i--) {
            numInLayer[i] += numInLayer[i+1];
            //cout<<"L "<<i<<' '<<numInLayer[i]<<'\n';
            sum+=numInLayer[i];
        }
        //cout<<"X "<<r<<' '<<sum<<'\n';
        ans=min(ans, sum);
    }
    cout<<ans<<'\n';
}

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