oj.uz

Submission #31888

# Submission time Handle Problem Language Result Execution time Memory
31888 2017-09-11T16:07:24 Z aome Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 2684 KB 
/*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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Correct 0 ms 2420 KB Output is correct
3 Correct 0 ms 2420 KB Output is correct
4 Correct 0 ms 2420 KB Output is correct
5 Correct 0 ms 2420 KB Output is correct
6 Correct 0 ms 2420 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Correct 0 ms 2420 KB Output is correct
3 Correct 0 ms 2420 KB Output is correct
4 Correct 0 ms 2420 KB Output is correct
5 Correct 0 ms 2420 KB Output is correct
6 Correct 0 ms 2420 KB Output is correct
7 Correct 3 ms 2420 KB Output is correct
8 Correct 0 ms 2420 KB Output is correct
9 Correct 0 ms 2420 KB Output is correct
10 Correct 3 ms 2420 KB Output is correct
11 Correct 3 ms 2420 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2420 KB Output is correct
2 Correct 0 ms 2420 KB Output is correct
3 Correct 0 ms 2420 KB Output is correct
4 Correct 0 ms 2420 KB Output is correct
5 Correct 0 ms 2420 KB Output is correct
6 Correct 0 ms 2420 KB Output is correct
7 Correct 3 ms 2420 KB Output is correct
8 Correct 0 ms 2420 KB Output is correct
9 Correct 0 ms 2420 KB Output is correct
10 Correct 3 ms 2420 KB Output is correct
11 Correct 3 ms 2420 KB Output is correct
12 Correct 16 ms 2552 KB Output is correct
13 Correct 13 ms 2684 KB Output is correct
14 Correct 376 ms 2552 KB Output is correct
15 Correct 166 ms 2552 KB Output is correct
16 Correct 1049 ms 2684 KB Output is correct
17 Execution timed out 1500 ms 2684 KB Execution timed out
18 Halted 0 ms 0 KB -