Submission #108881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
108881	2019-05-02T10:54:29 Z	Nodir_Bobiev	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

# include "dreaming.h"
# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

const long long NN = 1e5 + 100;

vector < pair < long long, long long > > gr[NN];
vector < pair < long long, long long > > cent;
bool used[NN];
long long d[NN], p[NN], mx, u;

void dfs( long long v, long long f )
{
	used[v] = true;
	for ( auto to: gr[v] ){
		if( to.first == f )
			continue;
		
		else{
			d[to.first] = d[v] + to.second;
			p[to.first] = v;
			
			if( mx < d[to.first] ){
				mx = d[to.first];
				u = to.first;
			}
			
			dfs( to.first, v );
		}
	}
}

pair < long long, long long >  getCenter( long long v, long long N )
{
	mx = u = 0;
	
	d[v] = 0;
	dfs( v, -1 );
	
	if( u == 0 )
		return {0, 0};
	
	v = u;
	d[v] = mx = u = 0;
	dfs( v, - 1 );
	
	long long D = mx;
	
	long long mn = 2e9;
	while( u != v ){
		
		if( d[u] >= (D + 1) / 2 )
			mn = min( mn, d[u] );
		
		if( (D - d[u]) >= (D + 1) / 2 )
			mn = min( mn, D - d[u] );
		
		u = p[u];
	}
	
	return {mn, D};
}


long long travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
	for ( long long i = 1; i <= M; i ++ ){
		A[i] ++; B[i] ++;
		gr[A[i]].push_back( {B[i], T[i]} );
		gr[B[i]].push_back( {A[i], T[i]} );
	}
	fill( used, used + N + 1, false );
	for ( long long i = 1; i <= N; i ++ ){
		if( used[i] == 0 ){
			cent.push_back( getCenter(i, N ) );
		}
		 
	}
	
	sort( cent.begin(), cent.end() );
	reverse( cent.begin(), cent.end() );
	
	long long answer = 0;
	for ( auto c: cent )
		answer = max( answer, c.second );
	
	if( M == N - 1 ){
		return cent[0].second;
	}

	else if ( M == N - 2 ){
		return max( answer, cent[0].first + cent[1].first + L ) ;
	}

	else {
		return max( max( cent[0].first + cent[1].first + L, cent[1].first + cent[2].first + 2 * L ), answer );
	} 
}
/*
int main()
{
	long long n, m, l;
	long long a[NN] = {}, b[NN] = {}, t[NN] = {};
	cin >> n >> m >> l;
	
	for ( long long i = 1; i <= m; i ++ ){
		cin >> a[i] >> b[i] >> t[i];
	}
	
	cout << travelTime( n, m, l, a, b, t );
	
	return 0;
}


8 7 100
0 1 4
1 3 2
1 2 1
1 4 4
3 5 3
3 6 4
2 7 6


4 2 50
0 1 100
1 2 100

7 3 1
0 1 4
2 3 4
4 5 4
*/

Compilation message

dreaming.cpp: In function 'long long int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:11: error: ambiguating new declaration of 'long long int travelTime(int, int, int, int*, int*, int*)'
 long long travelTime( int N, int M, int L, int A[], int B[], int T[] )
           ^~~~~~~~~~
In file included from dreaming.cpp:1:0:
dreaming.h:8:5: note: old declaration 'int travelTime(int, int, int, int*, int*, int*)'
 int travelTime(int N, int M, int L, int A[], int B[], int T[]);
     ^~~~~~~~~~