| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 206920 | oko | Dreaming (IOI13_dreaming) | 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<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,l,st1,st2,vis[100005],mn=1e10,dis[100005];
vector<pair<int,int> >gr[100005];
void dfs(int x)
{
vis[x]=1;
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first;
if(vis[u])continue;
dfs(u);
}
}
void cal(int x)
{
vis[x]=1;
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first,w=gr[x][i].second;
if(vis[u])continue;
cal(u);
dis[x]=max(dis[x],dis[u]+w);
}
}
void root(int x)
{
vis[x]=1;
mn=min(mn,dis[x]);
multiset<int>ms;
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first,w=gr[x][i].second;
if(vis[u])continue;
ms.insert(dis[u]+w);
}
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first,w=gr[x][i].second;
if(vis[u])continue;
ms.erase(ms.lower_bound(dis[u]+w));
long long oldx=dis[x],oldu=dis[u];
dis[x]=*--ms.end();
dis[u]=max(dis[u],oldx+w);
root(u);
dis[x]=oldx;
dis[u]=oldu;
}
}
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++)
{
gr[A[i]+1].push_back({B[i]+1,T[i]});
gr[B[i]+1].push_back({A[i]+1,T[i]});
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0&&st1==0)
{
dfs(i);
st1=i;
}
if(vis[i]==0&&st1)
{
dfs(i);
st2=i;
}
}
memset(vis,0,sizeof vis);
cal(st1);
memset(vis,0,sizeof vis);
root(st1);
long long ans=mn;
mn=1e10;
memset(vis,0,sizeof vis);
cal(st2);
memset(vis,0,sizeof vis);
root(st2);
return ans+mn;
}