Submission #39798

#	Time	Username	Problem	Language	Result	Execution time	Memory
39798		Pajaraja	Bosses (BOI16_bosses)	C++14	100 / 100	825 ms	2296 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
vector<int> g[5007];
bool vi[5007];
int dist[5007],n;
long long bfs(int s)
{
	queue<int> bfsq;
	bfsq.push(s);
	fill(vi,vi+5007,false);
	fill(dist,dist+5007,-1);
	vi[s]=true;
	dist[s]=0;
	while(!bfsq.empty())
	{
		int u=bfsq.front();
		for(int i=0;i<g[u].size();i++) if(!vi[g[u][i]])
		{
			vi[g[u][i]]=true;
			dist[g[u][i]]=dist[u]+1;
			bfsq.push(g[u][i]);
		}
		bfsq.pop();
	}
	long long sum=n;
	for(int i=1;i<=n;i++) 
	{
	    sum+=dist[i];
	    if(dist[i]==-1) return 1000000000000000000LL;
	}
	return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int t,z;
		scanf("%d",&t);
		for(int j=0;j<t;j++)
		{
			scanf("%d",&z);
			g[z].push_back(i);
		}
	}
	long long sol=1000000000000000000LL;
	for(int i=1;i<=n;i++) sol=fmin(sol,bfs(i));
	printf("%d",sol);
}

Compilation message (stderr)

bosses.cpp: In function 'long long int bfs(int)':
bosses.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) if(!vi[g[u][i]])
                ^
bosses.cpp: In function 'int main()':
bosses.cpp:48:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d",sol);
                 ^
bosses.cpp:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
bosses.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
                 ^
bosses.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&z);
                  ^

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