oj.uz

Submission #222974

# Submission time Handle Problem Language Result Execution time Memory
222974 2020-04-14T12:36:41 Z Lawliet Traffic (IOI10_traffic) C++14
0 / 100
 21 ms 23808 KB 
#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 = n - 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[]) 
{
	n = N;

	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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23680 KB Output is correct
2 Incorrect 21 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23680 KB Output is correct
2 Incorrect 21 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23680 KB Output is correct
2 Incorrect 21 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23680 KB Output is correct
2 Incorrect 21 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -