Submission #197401

#	Time	Username	Problem	Language	Result	Execution time	Memory
197401		Juney	Bosses (BOI16_bosses)	C++14	100 / 100	1012 ms	860 KiB

bosses

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e3 + 5;

int N, ans = 1e9;
vector<int> G[MAXN];
bool vis[MAXN];

int solve(int n) {
	memset(vis, 0, sizeof(vis));
	queue<pii> q; q.push(pii(n, 1));
	vis[n] = 1;
	int sum = 1, cnt = 0;
	while(!q.empty()) {
		int cur = q.front().fi, dep = q.front().se; q.pop();
		cnt++;
		for(auto nxt : G[cur]) if(!vis[nxt]) {
			vis[nxt] = 1;
			sum += dep + 1;
			q.push(pii(nxt, dep+1));
		}
	}
	if(cnt == N) return sum;
	return 1e9;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for(int i=1; i<=N; i++) {
		int x, y; cin >> x;
		for(int j=1; j<=x; j++) {
			cin >> y;
			G[y].push_back(i);	
		}
	}
	for(int i=1; i<=N; i++) ans = min(ans, solve(i));
	cout << ans;
}

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