| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 744550 | AtinaR | 꿈 (IOI13_dreaming) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
const int INF=(1<<30);
vector<pair<int,int> > graph[MAX];
vector<int> radius;
int dist[MAX];
int vis[MAX];
int FindEnd(int start, int status)
{
queue<int> q;
int index,max_dist;
index=start;max_dist=0;
q.push(start);
vis[start]=status;
dist[start]=0;
while(!q.empty())
{
int curr=q.front();
q.pop();
for(auto neighbour:graph[curr])
{
int newidx=neighbour.first;
int cost=neighbour.second;
if(vis[newidx]!=status)
{
vis[newidx]=status;
q.push(newidx);
dist[newidx]=dist[curr]+cost;
if(max_dist<dist[newidx])
{
max_dist=dist[newidx];
index=newidx;
}
}
}
}
return index;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int ans=0,tmp,end;
for(int i=0; i<M; i++)
{
int a=A[i];
int b=B[i];
int cena=T[i];
graph[a].push_back({b,cena});
graph[b].push_back({a,cena});
}
for(int i=0; i<N; i++)
{
if(vis[i]==0)
{
int y=FindEnd(i,1);
int x=FindEnd(y,2);
tmp=end=dist[x];
if(ans<tmp)
{
ans=tmp;
}
while(dist[x]>0)
{
for(int j=0; j<(int)graph[x].size(); j++)
{
y=graph[x][j].first;
if(dist[x]==dist[y]+graph[x][j].second)
{
x=y;
break;
}
}
tmp=min(tmp,max(dist[x],end-dist[x]));
}
radius.push_back(tmp);
}
}
sort(radius.begin(),radius.end());
if (radius.size() == 2) ans = max(ans,radius[0]+radius[1]+L);
else if (radius.size() > 2)
{
int last = max(radius[0]+radius[1],radius[1]+radius[2]+L);
last = min(max(radius[1]+radius[0],radius[0]+radius[2]+L),last);
last = min(max(radius[2]+radius[0],radius[0]+radius[1]+L),last);
ans = max(ans,last+L);
}
return ans;
}