oj.uz

Submission #41136

# Submission time Handle Problem Language Result Execution time Memory
41136 2018-02-13T05:05:58 Z ssnsarang2023 Bosses (BOI16_bosses) C++14
0 / 100
 2 ms 612 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) 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
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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