oj.uz

Submission #31889

# Submission time Handle Problem Language Result Execution time Memory
31889 2017-09-11T16:08:37 Z aome Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 2656 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 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() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int k; scanf("%d", &k);
		while (k--) {
			int x; scanf("%d", &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<int>&)':
bosses.cpp:48: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<int, int> >&)':
bosses.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
bosses.cpp: In function 'int main()':
bosses.cpp:95:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:97:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
                         ^
bosses.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
                          ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2260 KB Output is correct
2 Correct 0 ms 2260 KB Output is correct
3 Correct 0 ms 2260 KB Output is correct
4 Correct 0 ms 2260 KB Output is correct
5 Correct 0 ms 2260 KB Output is correct
6 Correct 0 ms 2260 KB Output is correct
7 Correct 3 ms 2260 KB Output is correct
8 Correct 0 ms 2260 KB Output is correct
9 Correct 0 ms 2260 KB Output is correct
10 Correct 3 ms 2260 KB Output is correct
11 Correct 3 ms 2260 KB Output is correct
12 Correct 9 ms 2392 KB Output is correct
13 Correct 6 ms 2392 KB Output is correct
14 Correct 343 ms 2392 KB Output is correct
15 Correct 143 ms 2392 KB Output is correct
16 Correct 899 ms 2524 KB Output is correct
17 Execution timed out 1500 ms 2656 KB Execution timed out
18 Halted 0 ms 0 KB -