제출 #595811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595811		Belphegor	Bosses (BOI16_bosses)	C++14	100 / 100	648 ms	656 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int>tree[5005];
int depth[5005];
int f(int root){
	memset(depth,0,sizeof(depth));
	depth[root] = 1;
	queue<int>q; q.push(root);
	int ret = 0;
	while(!q.empty()){
		int cur = q.front(); q.pop();
		ret+=depth[cur];
		for(int nxt:tree[cur]){
			if(depth[nxt]) continue;
			depth[nxt] = depth[cur]+1;
			q.push(nxt);
		}
	}
	for(int i=1; i<=n; i++) if(!depth[i]) return INT32_MAX;
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n;
	for(int i=1; i<=n; i++){
		int k; cin>>k;
		for(int j=0; j<k; j++){
			int x; cin>>x;
			tree[x].emplace_back(i);
		}
	}
	int ans = INT32_MAX;
	for(int i=1; i<=n; i++) ans = min(ans,f(i));
	cout<<ans;
}

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