제출 #43162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43162		win11905	Bosses (BOI16_bosses)	C++11	67 / 100	1553 ms	1384 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 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);
}

컴파일 시 표준 에러 (stderr) 메시지

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