oj.uz

답안 #108857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
108857 2019-05-02T10:12:34 Z Nodir_Bobiev 꿈 (IOI13_dreaming) C++14
0 / 100
 31 ms 3704 KB 
# include "dreaming.h"
# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

const int NN = 1e5 + 100;

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

void dfs( int v, int 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 < int, int >  getCenter( int v, int 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 );
	
	int D = mx;
	
	int 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};
}


int travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
	return 18;
	for ( int 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 ( int i = 1; i <= N; i ++ ){
		if( used[i] == 0 ){
			cent.push_back( getCenter(i, N ) );
			cout << cent.back().first << ' '<< cent.back().second << endl;
		}
		 
	}
	
	sort( cent.begin(), cent.end() );
	reverse( cent.begin(), cent.end() );
	
	if( M == N - 1 ){
		return cent.back().second;
	}

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

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

4 2 100
1 2 3
3 1 10


8 6 100
0 1 1
1 2 2
2 3 4
4 5 5
5 6 10
6 7 20
*/

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 3072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -