Submission #156296

#	Time	Username	Problem	Language	Result	Execution time	Memory
156296		Lawliet	Bosses (BOI16_bosses)	C++14	100 / 100	1039 ms	788 KiB

bosses

#include <bits/stdc++.h>

#define MAX 5010
#define INF 1000000010

using namespace std;

int n;
int n1, n2, qtd;

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

bool marc[MAX];

vector<int> grafo[MAX];

queue<int> q;

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

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

void BFS(int s)
{
	qtd = 0;
	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 );

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

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

Compilation message (stderr)

bosses.cpp: In function 'void BFS(int)':
bosses.cpp:42: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:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bosses.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n1);
   ~~~~~^~~~~~~~~~
bosses.cpp:62: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