oj.uz

답안 #43168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43168 2018-03-09T17:10:34 Z win11905 Bosses (BOI16_bosses) C++11
100 / 100
 1466 ms 1072 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 find(int x) {
	queue<int> Q;
	Q.emplace(x);
	chk[x] = x;
	stack<int> S;
	while(!Q.empty()) {
		auto u = Q.front(); Q.pop();
		S.emplace(u);
		for(auto v : g[u]) if(chk[v.x] != x) {
			chk[v.x] = chkn[v.y] = x;
			Q.push(v.x);
		}
	}
	while(!S.empty()) {
		auto u = S.top(); S.pop();
		dp[u] = 1;
		for(auto v : g[u]) if(chkn[v.y] == x) dp[u] += dp[v.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:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:44: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:46: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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 556 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 668 KB Output is correct
6 Correct 1 ms 668 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 556 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 668 KB Output is correct
6 Correct 1 ms 668 KB Output is correct
7 Correct 1 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 1 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 752 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 556 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 668 KB Output is correct
6 Correct 1 ms 668 KB Output is correct
7 Correct 1 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 1 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 9 ms 880 KB Output is correct
13 Correct 7 ms 880 KB Output is correct
14 Correct 292 ms 908 KB Output is correct
15 Correct 7 ms 908 KB Output is correct
16 Correct 1351 ms 1000 KB Output is correct
17 Correct 1431 ms 1000 KB Output is correct
18 Correct 1466 ms 1072 KB Output is correct