제출 #1275668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275668		random_user27	Bosses (BOI16_bosses)	C++20	100 / 100	396 ms	732 KiB

bosses

// In The Name Of God

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false),cin.tie(NULL))

const int maxn=5010;
const ll inf=1e15;
int dis[maxn];
vector<int>adj[maxn];
int n;

ll solve(int root){
	queue<int>qu;
	for(int i=1;i<=n;i++){
		dis[i]=0;
	}
	dis[root]=1;
	ll ans=0;
	qu.push(root);
	while(qu.size()){
		int v=qu.front();
		qu.pop();
		for(int i=0;i<adj[v].size();i++){
			if(dis[adj[v][i]]==0){
				dis[adj[v][i]]=dis[v]+1;
				qu.push(adj[v][i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==0){
			return inf;
		}
		ans+=dis[i];
	}
	return ans;
}

int main(){
	fast;
	cin>>n;
	for(int i=1;i<=n;i++){
		int sz;cin>>sz;
		for(int j=0;j<sz;j++){
			int a;cin>>a;
			adj[a].pb(i);
		}
	}
	ll ans=inf;
	for(int root=1;root<=n;root++){
		ans=min(ans,solve(root));
	}
	cout<<ans<<endl;
}

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