| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 259339 | uacoder123 | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int n,m,l,ans=0,vis[100001];
vector<iii> al[100001];
vi v;
int dfs(int node,int p)
{
vis[node]=1;
for(int i=0;i<al[node].size();++i)
{
if(!vis[al[node][i].S.F])
{
al[node][i].F=dfs(al[node][i].S.F,node);
al[node][i].F+=al[node][i].S.S;
}
}
sort(all(al[node]));
return(al[node].back().F);
}
void dfs2(int node,int p)
{
sort(all(al[node]));
int to=al[node].back().S.F;
ans=min(ans,al[node].back().F);
if(to==p)
return;
for(int i=0;i<al[to].size();++i)
{
if(al[to][i].S.F==node)
{
al[to][i].F=al[node][al[node].size()-2].F+al[to][i].S.S;
break;
}
}
dfs2(to,node);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
for(int i=0;i<m;++i)
{
al[A[i]].pb(mp(0,mp(B[i],T[i])));
al[B[i]].pb(mp(0,mp(A[i],T[i])));
}
for(int i=0;i<n;++i)
al[i].pb(mp(0,mp(i,i)));
for(int i=0;i<n;++i)
{
if(!vis[i])
{
dfs(i,i);
ans=1000000000;
dfs2(i,i);
v.pb(ans);
}
}
sort(all(v));
ans=v.back();
if(v.size()>1)
ans=v.back()+v[v.size()-2]+l;
if(v.size()>2)
ans=max(ans,2*l+v[v.size()-2]+v[v.size()-3]);
return(ans);
}