Submission #1308650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308650		KarolZ	Bosses (BOI16_bosses)	C++20	100 / 100	428 ms	752 KiB

bosses

#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;
	w[a].czy_odw=a;
	while(!q.empty()){
		a=q.front();
		q.pop();
		wyn+=w[a].gl;
		il++;
		for(int i=0;i<w[a].v.size();i++){
			if(w[w[a].v[i]].czy_odw==xd)continue;
			w[w[a].v[i]].czy_odw=xd;
			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;
}

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