Submission #538221

#	Time	Username	Problem	Language	Result	Execution time	Memory
538221		amunduzbaev	Bosses (BOI16_bosses)	C++17	100 / 100	670 ms	628 KiB

bosses

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

#define ar array

const int N = 5005;
vector<int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> k(n+1);
	for(int i=1;i<=n;i++){
		cin>>k[i];
		for(int j=0;j<k[i];j++){
			int x; cin>>x;
			edges[x].push_back(i);
		}
	}
	
	int res = n * n;
	for(int i=1;i<=n;i++){
		vector<int> d(n+1, n);
		queue<int> q; q.push(i);
		d[i] = 0;
		while(!q.empty()){
			int i=q.front(); q.pop();
			for(auto x : edges[i]){
				if(d[x] > d[i] + 1){
					d[x] = d[i] + 1;
					q.push(x);
				}
			}
		}
		
		bool ok = 1;
		int rr = n;
		for(int j=1;j<=n;j++){
			if(d[j] == n) ok = 0;
			rr += d[j];
		}
		
		if(ok) res = min(res, rr);
	}
	
	cout<<res<<"\n";
}

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