oj.uz

답안 #41138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41138 2018-02-13T05:18:19 Z ssnsarang2023 Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 1628 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];
bool vis[N];
vector<int> g[N], g2[N];

void dfs(int u, int &total) {
	sz[u] = 1;
	for (int v : g2[u]) {
		dfs(v, total);
		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 v : g[u]) {
			if (vis[v]) continue;
			++cnt, vis[v] = true;
			q.push(v);
			g2[u].push_back(v);
		}
	}
	if (cnt < n) return (int)1e9+7;
	int sum = 0;
	dfs(root, sum);
	return sum;
}

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:48:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:50: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:52: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 840 KB Output is correct
5 Correct 2 ms 840 KB Output is correct
6 Correct 2 ms 840 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 840 KB Output is correct
5 Correct 2 ms 840 KB Output is correct
6 Correct 2 ms 840 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 2 ms 940 KB Output is correct
11 Correct 2 ms 940 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 840 KB Output is correct
5 Correct 2 ms 840 KB Output is correct
6 Correct 2 ms 840 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 2 ms 940 KB Output is correct
11 Correct 2 ms 940 KB Output is correct
12 Correct 7 ms 1120 KB Output is correct
13 Correct 7 ms 1248 KB Output is correct
14 Correct 228 ms 1396 KB Output is correct
15 Correct 46 ms 1396 KB Output is correct
16 Correct 805 ms 1484 KB Output is correct
17 Execution timed out 1530 ms 1628 KB Time limit exceeded
18 Halted 0 ms 0 KB -