Submission #83422

#	Time	Username	Problem	Language	Result	Execution time	Memory
83422		Tusk	Bosses (BOI16_bosses)	C++14	100 / 100	688 ms	1304 KiB

bosses

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 5e3 + 5;

int n, ans = INT_MAX;
vector<vector<int> > g(N);
int dep[N];

int bfs(int root) {
	int ret = 0;
	queue<int> Q;
	for(int i = 1; i <= n; i++) dep[i] = INT_MAX;

	Q.emplace(root);
	dep[root] = 1;

	while(!Q.empty()) {
		int now = Q.front();
		Q.pop();

		for(int v : g[now]) if(dep[now] + 1 < dep[v]) {
			dep[v] = dep[now] + 1;
			Q.emplace(v);
		} 
	}
	for(int i = 1; i <= n; i++) {
		if(dep[i] == INT_MAX) return INT_MAX;
		ret += dep[i];
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 1, k; i <= n; i++) {
		scanf("%d", &k);
		while(k--) {
			int v;
			scanf("%d", &v);
			g[v].emplace_back(i);
		}
	} 

	for(int i = 1; i <= n; i++) ans = min(ans, bfs(i));
	printf("%d", ans);

	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
bosses.cpp:45:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v);
    ~~~~~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33