# 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[] )
{
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 ) );
}
}
sort( cent.begin(), cent.end() );
reverse( cent.begin(), cent.end() );
int 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()
{
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 );
}
/*
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
*/
Compilation message
dreaming.cpp:116:1: warning: "/*" within comment [-Wcomment]
/*
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
