Submission #358892

#	Time	Username	Problem	Language	Result	Execution time	Memory
358892		Bill_00	Bosses (BOI16_bosses)	C++14	100 / 100	850 ms	5356 KiB

bosses

#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pp push
#define MOD 1000000007
#define INF 1e18
#define N 200005
typedef long long ll;
using namespace std;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>adj[N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		int k;
		cin >> k;
		while(k--){
			int c;
			cin >> c;
			adj[c].pb(i);
		}
	}
	long long ans=1e18;
	for(int i=1;i<=n;i++){
		int cnt=0;
		long long res=0;
		bool vis[5001];
		memset(vis,0,sizeof(vis));
		queue<pair<ll,ll> >q;
		q.push({(ll)i,(ll)1});
		vis[i]=1;
		while(!q.empty()){
			cnt++;
			int node=q.front().ff;
			int height=q.front().ss;
			q.pop();
			res+=height;
			for(int j:adj[node]){
				if(vis[j]==0){
					vis[j]=1;
					q.push({j,height+1});
				}
			}
		}
		if(cnt==n) ans=min(ans,res);
	}
	cout << ans;
}

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