제출 #789807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789807		kayn	Bosses (BOI16_bosses)	C++14	100 / 100	391 ms	672 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
using namespace std;
vector<ll> adj[5010];

int main(){
	int n; cin >> n;
	for(int i=1; i<=n; i++){
		int k; cin >> k;
		for(int j=0; j<k; j++){
			int a; cin >> a;
			adj[a].pb(i); // k bisa jadi child dr a
		}
	}
	ll ans=100000000;
	for(int i=1; i<=n; i++){ //nyobain satu satu yg jd root nya
		int depth[5010]; memset(depth, 0, sizeof(depth));
		bool vis[5010]; memset(vis, 0, sizeof(vis));
		int lvl[5010]; memset(lvl, 0, sizeof(lvl));
		queue<int> q;
		q.push(i);
		vis[i]=1; depth[1]=1; lvl[i]=1;
		int batas=1;
		while(!q.empty()){
		int cur = q.front(); q.pop();
			for(auto j : adj[cur]){
				if(vis[j]) continue;
				lvl[j]=lvl[cur]+1; batas=max(batas, lvl[j]);
				depth[lvl[j]]++;
				vis[j]=1; 
				q.push(j);
			}
		}
		bool bisa=1;
		for(auto i=1; i<=n; i++){
			if(!vis[i]){
				bisa=0; break;
			}
		}
		if(!bisa) continue;
		ll sum[batas+10], total=0;
		sum[batas+1]=0;
		for(int i=batas; i>=1; i--){
			sum[i]=depth[i]+sum[i+1];
			total +=sum[i];
		}
		ans=min(ans, total);
	}
	cout << ans << endl;
	return 0;
}

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