Submission #222976

#	Time	Username	Problem	Language	Result	Execution time	Memory
222976		Lawliet	Traffic (IOI10_traffic)	C++14	0 / 100	20 ms	23808 KiB

traffic

#include "traffic.h"
#include "bits/stdc++.h"

using namespace std;

const int MAXN = 1000010;
 
int n;
int optNode;
int optValue = MAXN;

int sub[MAXN];

vector< int > adj[MAXN];

void DFSInit(int cur, int p)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFSInit( viz , cur );

		sub[cur] += sub[viz];
	}
}

void DFSCalculate(int cur, int p)
{
	int curValue = sub[0] - sub[cur];

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

		if( viz != p )
			curValue = max( curValue , sub[viz] );
	}

	if( curValue < optValue )
	{
		optNode = cur;
		optValue = curValue;
	}

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

		if( viz != p )
			DFSCalculate( viz , cur );
	}
}

int LocateCentre(int N, int P[], int S[], int D[]) 
{
	for(int i = 0 ; i < N ; i++)
		sub[i] = P[i];

	for(int i = 0 ; i < N - 1 ; i++)
	{
		adj[ S[i] ].push_back( D[i] );
		adj[ D[i] ].push_back( S[i] );
	}

	DFSInit( 1 , 0 );
	DFSCalculate( 1 , 0 );
	
	return optNode;
}

Compilation message (stderr)

traffic.cpp: In function 'void DFSInit(int, int)':
traffic.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
traffic.cpp: In function 'void DFSCalculate(int, int)':
traffic.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
traffic.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25