Submission #134576

#	Time	Username	Problem	Language	Result	Execution time	Memory
134576		junodeveloper	Bosses (BOI16_bosses)	C++14	100 / 100	989 ms	760 KiB

bosses

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
int n, D[5010], C[5010];
vector<int> adj[5010];
int main() {
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		int k;
		scanf("%d",&k);
		for(j=1;j<=k;j++) {
			int x;
			scanf("%d",&x);
			adj[x].push_back(i);
		}
	}
	queue<int> q;
	int u,mx,tot,res=2e9;
	for(i=1;i<=n;i++) {
		fill(D+1,D+n+1,-1);
		fill(C,C+n+1,0);
		mx=D[i]=0; q.push(i);
		tot=0;
		while(!q.empty()) {
			u=q.front();q.pop();
			C[D[u]]++; mx=max(mx,D[u]);
			tot++;
			for(auto& it:adj[u]){
				if(D[it]==-1) {
					D[it]=D[u]+1;
					q.push(it);
				}
			}
		}
		if(tot<n) continue;
		int v=0;
		for(j=mx;j>=0;j--) {
			C[j]+=C[j+1];
			v+=C[j];
		}
		res=min(res,v);
	}
	printf("%d",res);
	return 0;
}

Compilation message (stderr)

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

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