Submission #43168

#	Time	Username	Problem	Language	Result	Execution time	Memory
43168		win11905	Bosses (BOI16_bosses)	C++11	100 / 100	1466 ms	1072 KiB

bosses

#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 (stderr)

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33