oj.uz

Submission #39798

# Submission time Handle Problem Language Result Execution time Memory
39798 2018-01-18T17:58:47 Z Pajaraja Bosses (BOI16_bosses) C++14
100 / 100
 825 ms 2296 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2164 KB Output is correct
2 Correct 0 ms 2164 KB Output is correct
3 Correct 0 ms 2164 KB Output is correct
4 Correct 0 ms 2164 KB Output is correct
5 Correct 0 ms 2164 KB Output is correct
6 Correct 0 ms 2164 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2164 KB Output is correct
2 Correct 0 ms 2164 KB Output is correct
3 Correct 0 ms 2164 KB Output is correct
4 Correct 0 ms 2164 KB Output is correct
5 Correct 0 ms 2164 KB Output is correct
6 Correct 0 ms 2164 KB Output is correct
7 Correct 1 ms 2164 KB Output is correct
8 Correct 1 ms 2164 KB Output is correct
9 Correct 0 ms 2164 KB Output is correct
10 Correct 1 ms 2164 KB Output is correct
11 Correct 0 ms 2164 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2164 KB Output is correct
2 Correct 0 ms 2164 KB Output is correct
3 Correct 0 ms 2164 KB Output is correct
4 Correct 0 ms 2164 KB Output is correct
5 Correct 0 ms 2164 KB Output is correct
6 Correct 0 ms 2164 KB Output is correct
7 Correct 1 ms 2164 KB Output is correct
8 Correct 1 ms 2164 KB Output is correct
9 Correct 0 ms 2164 KB Output is correct
10 Correct 1 ms 2164 KB Output is correct
11 Correct 0 ms 2164 KB Output is correct
12 Correct 7 ms 2296 KB Output is correct
13 Correct 6 ms 2296 KB Output is correct
14 Correct 172 ms 2296 KB Output is correct
15 Correct 25 ms 2296 KB Output is correct
16 Correct 771 ms 2296 KB Output is correct
17 Correct 825 ms 2296 KB Output is correct
18 Correct 824 ms 2296 KB Output is correct