oj.uz

Submission #31887

# Submission time Handle Problem Language Result Execution time Memory
31887 2017-09-11T15:52:37 Z aome Bosses (BOI16_bosses) C++14
0 / 100
 0 ms 2420 KB 
/*input
4
1 4
3 1 3 4
2 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);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		visited[u] = true;
		for (auto v : g[u]) {
			if (visited[v]) continue;
			a[u].push_back(v);
			q.push(v);
		}
	}
	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

bosses.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
bosses.cpp:41: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:49: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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Incorrect 0 ms 2420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Incorrect 0 ms 2420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Incorrect 0 ms 2420 KB Output isn't correct
3 Halted 0 ms 0 KB -