제출 #693821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693821		amirhoseinfar1385	Bosses (BOI16_bosses)	C++17	100 / 100	737 ms	700 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=5000+5;
vector<int>adj[maxn];
vector<int>dis;

bool caldij(int u){
	vector<int>vis(n+1);
	vector<int>bf;
	bf.push_back(u);
	int len=0;
	while((int)bf.size()>0){
		for(auto x:bf){
			vis[x]=1;
		//	cout<<u<<" "<<x<<" "<<len<<endl;
			dis[x]=len;
		}
		vector<int>fake;
		for(auto x:bf){
			for(auto y:adj[x]){
				if(vis[y]==0){
					vis[y]=1;
					fake.push_back(y);
		//			cout<<u<<" "<<y<<endl;
				}
			}
		}
		bf.swap(fake);
		len++;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			return 0;
		}
	}
	return 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		for(int j=0;j<k;j++){
			int d;
			cin>>d;
			adj[d].push_back(i);
		}
	}	
	long long mainres=1e16;
	for(int i=1;i<=n;i++){
		dis.clear();
		dis.resize(n+1);
		if(caldij(i)==0){
			continue;
		}
		long long fake=0;
		for(int j=1;j<=n;j++){
			fake+=dis[j];
		}
		//cout<<i<<" "<<fake<<"\n";
		mainres=min(mainres,fake);
	}
	mainres+=n;
	cout<<mainres<<"\n";
}

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