Submission #253829

#	Time	Username	Problem	Language	Result	Execution time	Memory
253829		ChrisT	Bosses (BOI16_bosses)	C++17	100 / 100	694 ms	760 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
vector<int> canChild[5005];
int dist[5005];
int main () {
	int n;
	scanf ("%d",&n);
	for (int i = 1; i <= n; i++) {
		int k; scanf ("%d",&k);
		while (k--) {
			int a; scanf ("%d",&a); canChild[a].push_back(i);
		}
	}
	int ret = INT_MAX;
	for (int rt = 1; rt <= n; rt++) {
		memset(dist,0x3f,sizeof dist);
		queue<int> q;
		q.push(rt); int sz = 0, ans = 0; dist[rt] = 1;
		while (!q.empty()) {
			int cur = q.front(); q.pop();
			++sz; ans += dist[cur];
			for (int i : canChild[cur]) if (dist[cur] + 1 < dist[i]) {
				dist[i] = dist[cur] + 1;
				q.push(i);
			}
		}
		if (sz == n) ret = min(ret,ans);
	}
	printf ("%d\n",ret);
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:7:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&n);
  ~~~~~~^~~~~~~~~
bosses.cpp:9:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf ("%d",&k);
          ~~~~~~^~~~~~~~~
bosses.cpp:11:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int a; scanf ("%d",&a); canChild[a].push_back(i);
           ~~~~~~^~~~~~~~~

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