제출 #1102468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102468		sinataghizadeh	Bosses (BOI16_bosses)	C++14	100 / 100	544 ms	856 KiB

bosses

#include <bits/stdc++.h>
 using namespace std;


typedef long long       ll;
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pll;
#define all(x)			(x).begin(),(x).end()
#define pb    			push_back
#define fi              first
#define se              second
#define beg             begin
#define siz              size()
#define fastio          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define endl       		'\n'
#define ins             insert
#define log             LOG
const ll inf = 1e9;
const ll mod = 10289;
const int maxn=5004+6;
const int log=24;
ll n,ans,mn=inf,sum[maxn],par[maxn],dis[maxn];
vector<ll>adj[maxn];
void bfs(ll x){
	queue<ll>q;
//	vector<ll>a;
	q.push(x);
	while(q.siz){
		ll v=q.front();
//		a.pb(v);
		q.pop();
		for(auto u:adj[v]){
			if(dis[u]==-1){
				dis[u]=dis[v]+1;
	//			par[u]=v;
				q.push(u);
			}
		}
	}
//	reverse(all(a));
	for(int i=1;i<=n;i++){
		ans+=dis[i];
		if(dis[i]==-1){
			ans=1000000000000;return;
		}
	}
}
int main(){
	fastio
	cin>>n;
	for(int i=1;i<=n;i++){
		ll k;
		cin>>k;
		while(k--){
			ll u;
			cin>>u;
			adj[u].pb(i);
		}
	}
	for(int i=1;i<=n;i++){
	//	fill(sum,sum+n+2,1);
		fill(dis,dis+maxn,-1);
		ans=0;dis[i]=1;
		bfs(i);
		mn=min(mn,ans);
	}
	cout<<mn<<endl;
}

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