| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 742052 | angels | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
return 0;
}