Submission #108904

#	Time	Username	Problem	Language	Result	Execution time	Memory
108904		Nodir_Bobiev	Dreaming (IOI13_dreaming)	C++14	100 / 100	168 ms	17060 KiB

dreaming

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

using namespace std;

const int NN = 1e5 + 100;

vector < pair < int, long long > > gr[NN];
vector < pair < long long, long long > > rads;
long long dist1[NN], dist2[NN], dia, rad, u;
bool used[NN];

void dfs( int v, int f, int c )
{
	used[v] = true;
	for ( auto to: gr[v] ){
		if( to.first == f )
			continue;
		else{
			long long dst = 0;
			if( c == 1 ){
				dist1[to.first] = dist1[v] + to.second;
				dst = dist1[to.first];
			}
			else{
				dist2[to.first] = dist2[v] + to.second;
				dst = dist2[to.first];
			}
			if( dia < dst ){
				dia = dst;
				u = to.first;
			}
			dfs( to.first, v, c );
		}
	}
}

void jfs( int v, int f )
{
	rad = min( rad, max( dist1[v], dist2[v] ) );
	for ( auto to: gr[v] ){
		if( to.first == f )
			continue;
		else{
			jfs( to.first, v );
		}
	}
}

pair < long long, long long > get( int v )
{
	dia = 0; u = 0;
	dist1[v] = 0;
	dfs( v, -1, 1 );
	
	if( u == 0 )return {0, 0};
	
	v = u; dia = 0;
	
	dist1[v] = 0;
	dfs( v, -1, 1 );
	
	dist2[u] = 0;
	dfs( u, -1, 2 );
	
	rad = 1e18;
	jfs( v, -1 );
	return make_pair( rad, dia );	
}

int travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
	for ( int i = 0; i < M; i ++ ){
		gr[A[i]].push_back( { B[i], T[i] } );
		gr[B[i]].push_back( { A[i], T[i] } );
	}
	
	for ( int i = 0; i < N; i ++ ){
		if( used[i] ) continue;
		
		rads.push_back( get( i ) );
		//cout << rads.back().first << ' '<< rads.back().second << endl;
	}
	
	sort( rads.begin(), rads.end() );
	reverse( rads.begin(), rads.end() );
	long long MaxDiameter = 0;
	for ( auto rd: rads )
		MaxDiameter = max( MaxDiameter, rd.second );
	
	if( rads.size() == 1 )
		return rads.back().second;
	
	else if( rads.size() == 2 )
		return max( MaxDiameter, rads[0].first + rads[1].first + L);
	
	else 
		return max( MaxDiameter, max( rads[0].first + rads[1].first + L, rads[1].first + rads[2].first + L + L ) );
}
/*
int main()
{
	int n, m, l;
	cin >> n >> m >> l;
	int a[NN] = {}, b[NN] = {}, t[NN] = {};
	
	for ( int i = 0; i < m; i ++ ){
		cin >> a[i] >> b[i] >> t[i];
	}
	
	cout << travelTime( n, m, l, a, b, t );
}
/*
6 3 14
0 1 8
1 2 8
4 5 8
*/

Compilation message (stderr)

dreaming.cpp:115:1: warning: "/*" within comment [-Wcomment]
 /*

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23