Submission #1152789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152789		tegshee	Bosses (BOI16_bosses)	C++20	100 / 100	400 ms	3012 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ss second
#define ff first
#define pb push_back
const int mxn=1e5+5; 
int n,res=1e12,d[mxn];
vector<int> g[mxn];
void bfs(int k) {
    for(int i=1; i<=n; i++)  d[i]=1e12;
    queue<int> q;
    q.push(k);
    d[k]=1;
    int u=0;
    while(!q.empty()) { 
        int x=q.front();
        q.pop();
        u+=d[x];
        for(int u:g[x]) {
            if(d[u]>d[x]+1) {
                d[u]=d[x]+1;
                q.push(u);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(d[i]==1e12) u=1e12;
    }
    res=min(res,u);
} 
signed main () {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int s;  
		cin>>s;
        while(s--) {
            int v;
            cin>>v;
            g[v].pb(i);
        }
    }
    for(int i=1; i<=n; i++)  bfs(i);
    cout<<res;
}

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