Submission #1308649

#TimeUsernameProblemLanguageResultExecution timeMemory
1308649KarolZBosses (BOI16_bosses)C++20
0 / 100
1 ms568 KiB
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct wi{
	vector<int>v;
	int gl=0;
	int czy_odw=0;
}*w;
int n;
int spr(int a){
	w[a].gl=0;
	int wyn=0;
	queue<int>q;
	int il=0;
	q.push(a);
	int xd=a;
	while(!q.empty()){
		a=q.front();
		q.pop();
		if(w[a].czy_odw==xd)continue;
		w[a].czy_odw=xd;
		wyn+=w[a].gl;
		il++;
		for(int i=0;i<w[a].v.size();i++){
			w[w[a].v[i]].gl=w[a].gl+1;
			q.push(w[a].v[i]);
		}
	}
	return (il==n)?wyn:1000000000;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
	int k,v1,minn=1000000000;
	cin>>n;
	w=new wi[n+1];
	for(int i=1;i<=n;i++){
		cin>>k;
		for(int j=0;j<k;j++){
			cin>>v1;
			w[v1].v.push_back(i);
		}
	}
	for(int i=1;i<=n;i++)minn=min(minn,spr(i));
	cout<<minn+n;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...