Submission #422143

#	Time	Username	Problem	Language	Result	Execution time	Memory
422143		victoriad	Bosses (BOI16_bosses)	C++14	100 / 100	734 ms	708 KiB

bosses

#include <cmath>
#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;
 int x,t;
 void bfs(vector<vector<int> >&g,int n,int y){
	 queue<int>q;
	 q.push(n);
	 vector<int>s(y,1e9);
	 s[n]=1;
	 while(!q.empty()){
		 t++;
		 int a=q.front();
		 q.pop();
		 for(int i:g[a]){
			 if(s[i]>s[a]+1){
				 s[i]=s[a]+1;
				 x+=s[i];
				 q.push(i);
			 }
		 }
	 }
 }


int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k,a;
	cin>>n;
	vector<vector<int> >em(n);
	int r=-1;
	for(int i=0;i<n;i++){
		cin>>k;
		while(k--){
			cin>>a;
			a--;
			em[a].push_back(i);
		}
	}
	int ans=1e9;
	for(int i=0;i<n;i++){
		x=1;
		t=0;
		bfs(em,i,n);
		if(t==n){
		ans=min(x,ans);
		}
	}
	cout<<ans<<"\n";
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:38:6: warning: unused variable 'r' [-Wunused-variable]
   38 |  int r=-1;
      |      ^

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