oj.uz

Submission #41140

# Submission time Handle Problem Language Result Execution time Memory
41140 2018-02-13T05:21:02 Z ssnsarang2023 Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 1260 KB 
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define SZ(x) ((int)x.size())

const int N = 5e3+5;
int n, sz[N], total;
bool vis[N];
vector<int> g[N], g2[N];

void dfs(int u) {
	sz[u] = 1;
	for (int i = 0; i < SZ(g2[u]); ++i) {
		int v = g2[u][i];
		dfs(v);
		sz[u] += sz[v];
	}
	total += sz[u];
}

int make_tree(int root) {
	for (int i = 1; i <= n; ++i) vis[i] = false, g2[i].clear();
	queue<int> q;
	q.push(root);
	vis[root] = 1;
	int cnt = 1;
	while (SZ(q)) {
		int u = q.front(); q.pop();
		for (int i = 0; i < SZ(g[u]); ++i) {
			int v = g[u][i];
			if (vis[v]) continue;
			++cnt, vis[v] = true;
			q.push(v);
			g2[u].push_back(v);
		}
	}
	if (cnt < n) return (int)1e9+7;
	total = 0;
	dfs(root);
	return total;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int m; scanf("%d", &m);
		for (int j = 1, v; j <= m; ++j) {
			scanf("%d", &v);
			g[v].push_back(i);
		}
	}
	int res = (int)1e9+7;
	for (int i = 1; i <= n; ++i)
		res = min(res, make_tree(i));
	printf("%d", res);
	return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:50:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:52:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int m; scanf("%d", &m);
                         ^
bosses.cpp:54:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v);
                   ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 1 ms 660 KB Output is correct
4 Correct 1 ms 732 KB Output is correct
5 Correct 1 ms 804 KB Output is correct
6 Correct 1 ms 804 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 1 ms 660 KB Output is correct
4 Correct 1 ms 732 KB Output is correct
5 Correct 1 ms 804 KB Output is correct
6 Correct 1 ms 804 KB Output is correct
7 Correct 1 ms 804 KB Output is correct
8 Correct 2 ms 804 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 804 KB Output is correct
11 Correct 2 ms 804 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 1 ms 660 KB Output is correct
4 Correct 1 ms 732 KB Output is correct
5 Correct 1 ms 804 KB Output is correct
6 Correct 1 ms 804 KB Output is correct
7 Correct 1 ms 804 KB Output is correct
8 Correct 2 ms 804 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 804 KB Output is correct
11 Correct 2 ms 804 KB Output is correct
12 Correct 8 ms 880 KB Output is correct
13 Correct 6 ms 880 KB Output is correct
14 Correct 211 ms 1132 KB Output is correct
15 Correct 36 ms 1132 KB Output is correct
16 Correct 846 ms 1260 KB Output is correct
17 Execution timed out 1540 ms 1260 KB Time limit exceeded
18 Halted 0 ms 0 KB -