oj.uz

Submission #43162

# Submission time Handle Problem Language Result Execution time Memory
43162 2018-03-09T16:59:11 Z win11905 Bosses (BOI16_bosses) C++11
67 / 100
 1500 ms 1384 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int MAXN = 5e3 + 5, MAXM = 1e4 + 5;

int n, chk[MAXN], chkn[MAXM], dp[MAXN];
vector<pii> g[MAXN];

int dfs(int u, int x) {
	int sum = 0;
	for(auto v : g[u]) if(chkn[v.y] == x) {
		sum += dfs(v.x, x);
	}
	return dp[u] = ++sum;
}

int find(int x) {
	queue<int> Q;
	Q.emplace(x);
	chk[x] = x;
	while(!Q.empty()) {
		auto u = Q.front(); Q.pop();
		for(auto v : g[u]) if(chk[v.x] != x) {
			chk[v.x] = chkn[v.y] = x;
			Q.push(v.x);
		}
	}
	dfs(x, x);
	int sum = 0; for(int i = 1; i <= n; ++i) {
		if(chk[i] != x) return 1000000000;
		sum += dp[i];
	}
	return sum;
}

int main() {
	#ifdef INPUT
	freopen("r", "r", stdin);
	#endif
	scanf("%d", &n);
	int idx = 1;
	for(int i = 1; i <= n; ++i) {
		int t; scanf("%d", &t);
		while(t--) {
			int x; scanf("%d", &x);
			g[x].emplace_back(i, idx++);
		}
	}
	int mn = 1e9;
	for(int i = 1; i <= n; ++i) {
		int now = find(i);
		mn = min(mn ,now);
	}
	printf("%d\n", mn);
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:46:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
                         ^
bosses.cpp:48: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 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 1 ms 580 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 1 ms 696 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 1 ms 580 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 752 KB Output is correct
8 Correct 2 ms 788 KB Output is correct
9 Correct 2 ms 792 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Correct 2 ms 796 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 1 ms 580 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 752 KB Output is correct
8 Correct 2 ms 788 KB Output is correct
9 Correct 2 ms 792 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Correct 2 ms 796 KB Output is correct
12 Correct 11 ms 964 KB Output is correct
13 Correct 7 ms 1040 KB Output is correct
14 Correct 303 ms 1232 KB Output is correct
15 Correct 7 ms 1248 KB Output is correct
16 Correct 1415 ms 1320 KB Output is correct
17 Execution timed out 1553 ms 1384 KB Time limit exceeded
18 Halted 0 ms 0 KB -