| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 742056 | angels | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<algorithm>
#include<vector>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
int a, b;
long long int L, t;
long long int ans;
vector< pair< int, long long int > > E[100002];
long long int Aa[100002], XX;
int color, x;
long long int maxi, mini;
int vis[100002];
void lejano( int node, long long int d ){
if( d > maxi ){
maxi = d;
x = node;
}
vis[node] = color;
for( int i = 0; i < E[node].size(); i++ )
if( vis[ E[node][i].first ] != color )
lejano( E[node][i].first, d + E[node][i].second );
}
long long int dist[100002];
void DFS( int node, long long int d, int c ){
if( c ){
dist[node] = max( dist[node], d );
maxi = max( maxi, dist[node] );
mini = mini == -1 ? dist[node] : min( mini, dist[node] );
} else {
dist[node] = d;
}
vis[node] = color;
for( int i = 0; i < E[node].size(); i++ )
if( vis[ E[node][i].first ] != color )
DFS( E[node][i].first, d + E[node][i].second, c );
}
long long int checkTree( int r ){
int a, b;
color++; maxi = -1; x = 0;
lejano( r, 0 );
a = x;
color++; maxi = -1; x = 0;
lejano( a, 0 );
b = x;
maxi = -1; mini = -1;
color++;
DFS( a, 0, 0 );
color++;
DFS( b, 0, 1 );
ans = max( ans, maxi );
return mini;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
optimizar_io
//cin >> n >> m >> L;
n=N; m=M;
for( int i = 0; i < m; i++ ){
//cin >> a >> b >> t;
a=A[i]; b=B[i]; t=T[i];
E[a].push_back( make_pair( b, t ) );
E[b].push_back( make_pair( a, t ) );
}
for( int i = 0; i < n; i++ )
if( !vis[i] )
Aa[++XX] = checkTree( i );
sort( Aa + 1, Aa + XX + 1 );
reverse( Aa + 1, Aa + XX + 1 );
if( XX > 1 ){
ans = max( ans, Aa[1] + Aa[2] + L );
if( XX > 2 )
ans = max( ans, Aa[2] + Aa[3] + 2 * L );
}
return(ans);
}