Submission #98967

#	Time	Username	Problem	Language	Result	Execution time	Memory
98967		zicon35	Bosses (BOI16_bosses)	C++14	100 / 100	617 ms	888 KiB

bosses

#include<bits/stdc++.h>

using namespace std;

int n,k,v;
vector< vector<int>> adj;

int d[20005];

int bfs(int root) {

	memset(d, -1, sizeof d);
	queue<int> Q;
	Q.push(root);
	d[root] = 1;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
 
		for(auto i : adj[x]) {
			if(d[i] == -1) {
				d[i] = 1 + d[x];
				Q.push(i);
			}
		}
	}
	int a = 0;
	for(int i = 1; i <= n; i++) {
		if(d[i] == -1) return -1;
		else a += d[i];
	}
	return a;
}

int solve(){
    int k,v;
    cin>>n;
    adj.resize(n+2);
    for(int i=1;i<=n;i++){
       cin>>k;
       for(int j=1;j<=k;j++){
            cin>>v;
            adj[v].push_back(i);
       } 
    }

    int ans = INT_MAX; 
    for(int i=1;i<=n;i++){
        int x = bfs(i);
        if(x == -1) continue;
        ans = min(ans,x);
    }
    return ans;
}

int main(){

    cout<<solve()<<endl;
    return 0;
}

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