Submission #208171

#	Time	Username	Problem	Language	Result	Execution time	Memory
208171		pavement	Bosses (BOI16_bosses)	C++17	100 / 100	1422 ms	1120 KiB

bosses

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

int N, A = 1e9, T;
bitset<5005> V;
vector<int> adj[5005], nadj[5005];
queue<int> Q;

int dfs(int n, int e) {
	int d = 1;
	for (auto u : nadj[n])
		if (u ^ e) d += dfs(u, n);
	T += d;
	return d;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1, K, X; i <= N; i++) {
		cin >> K;
		while (K--) {
			cin >> X;
			adj[X].push_back(i);
		}
	}
	for (int i = 1; i <= N; i++) {
		V.reset();
		T = 0;
		for (int j = 1; j <= N; j++) nadj[j].clear();
		Q.push(i);
		V[i] = 1;
		while (!Q.empty()) {
			int a = Q.front();
			Q.pop();
			for (auto u : adj[a])
				if (!V[u]) {
					V[u] = 1;
					nadj[a].push_back(u);
					Q.push(u);
				}
		}
		if ((int)V.count() ^ N) continue;
		dfs(i, -1);
		A = min(A, T);
	}
	cout << A << '\n';
}

Compilation message (stderr)

bosses.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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