Submission #146228

#	Time	Username	Problem	Language	Result	Execution time	Memory
146228		Diuven	Bosses (BOI16_bosses)	C++14	100 / 100	1088 ms	1116 KiB

bosses

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

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 5010;
const lint LNF = 2e18;

int n;
vector<int> G[MAX], R[MAX];

int solve(int r){
	int res = 1;
	queue<int> Q;
	int dep[MAX] = {};
	dep[r] = 1; Q.push(r);
	while(!Q.empty()){
		int v; v=Q.front(); Q.pop();
		for(int x:R[v]){
			if(dep[x]) continue;
			Q.push(x); dep[x] = dep[v]+1;
			res += dep[x];
		}
	}
	for(int i=1; i<=n; i++) if(dep[i]==0) return INF;
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n;
	for(int i=1; i<=n; i++){
		int k, x; cin>>k;
		for(int j=1; j<=k; j++) cin>>x, G[i].push_back(x), R[x].push_back(i);
	}

	int ans = INF;
	for(int i=1; i<=n; i++) ans = min(ans, solve(i));

	cout<<ans<<'\n';

	return 0;
}

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