Submission #31888

#	Time	Username	Problem	Language	Result	Execution time	Memory
31888		aome	Bosses (BOI16_bosses)	C++14	67 / 100	1500 ms	2684 KiB

bosses

/*input
6
2 6 5
3 4 6 3
2 4 1
4 5 3 1 6
5 2 4 6 3 1
3 2 5 3

4
0
1 1
1 2
1 3
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 5005
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n;
vector<vector<int> > g(N);
vector<vector<int> > a(N);
bool visited[N];
int curans = 0;
int dfs(int u, int p) {
	int ret = 0;
	for (auto v : a[u]) {
		if (v == p) continue;
		ret += dfs(v, u);
	}
	curans += ret + 1;
	return ret + 1;
}

int cal(int root) {
	a.assign(N, vector<int>());
	memset(visited, 0, sizeof(visited));
	queue<int> q;
	q.push(root); visited[root] = true;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v : g[u]) {
			if (visited[v]) continue;
			a[u].push_back(v);
			q.push(v); visited[v] = true;
		}
	}
	for (int i = 1; i <= n; i++) if (!visited[i]) return -1;
	curans = 0;
	dfs(root, root);
	return curans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k; cin >> k;
		while (k--) {
			int x; cin >> x;
			g[x].push_back(i);
		}
	}
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		int rec = cal(i); if (rec == -1) continue;
		if (ans == -1) ans = rec;
		else ans = min(ans, rec);
	}
	cout << ans << endl;
}

Compilation message (stderr)

bosses.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
bosses.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
bosses.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
bosses.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^

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