oj.uz

Submission #43160

# Submission time Handle Problem Language Result Execution time Memory
43160 2018-03-09T16:55:26 Z win11905 Bosses (BOI16_bosses) C++11
0 / 100
 2 ms 616 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) 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:40:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:43: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:45: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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Incorrect 2 ms 616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Incorrect 2 ms 616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Incorrect 2 ms 616 KB Output isn't correct
5 Halted 0 ms 0 KB -