Submission #156295

#	Time	Username	Problem	Language	Result	Execution time	Memory
156295		Lawliet	Bosses (BOI16_bosses)	C++14	100 / 100	1035 ms	840 KiB

bosses

#include <bits/stdc++.h>

#define MAX 5010
#define INF 1000000010

using namespace std;

int n;
int n1, n2;

int ans[MAX];
int dist[MAX];

bool marc[MAX];

vector<int> grafo[MAX];

queue<int> q;

void add(int cur, int root, int d)
{
	q.push( cur );
	dist[ cur ] = d;
	marc[ cur ] = true;

	ans[ root ] += dist[ cur ];
}

void BFS(int s)
{
	memset(marc , 0 , sizeof( marc ));

	add( s , s , 1 );

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		for(int i = 0 ; i < grafo[ cur ].size() ; i++)
		{
			int prox = grafo[ cur ][ i ];

			if( !marc[prox] )
				add( prox , s , dist[ cur ] + 1 );
		}
	}
}

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d",&n1);

		for(int j = 1 ; j <= n1 ; j++)
		{
			scanf("%d",&n2);

			grafo[ n2 ].push_back( i );
		}
	}

	int mn = INF;

	for(int i = 1 ; i <= n ; i++)
	{
		BFS( i );

		bool reachAll = true;

		for(int j = 1 ; j <= n ; j++)
			reachAll = reachAll && marc[ j ];

		if( reachAll ) mn = min(mn , ans[ i ]);
	}

	printf("%d\n",mn);
}

Compilation message (stderr)

bosses.cpp: In function 'void BFS(int)':
bosses.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bosses.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n1);
   ~~~~~^~~~~~~~~~
bosses.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&n2);
    ~~~~~^~~~~~~~~~

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