| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 520300 | new_acc | 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>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
vector<pair<int,int> >graf[N];
int naj1,naj2;
bool vis[N];
int oo[N];
int xdd;
void dfs(int v,int odl){
if(vis[v]) return;
vis[v]=1;
if(odl>=naj1) naj1=odl,naj2=v;
for(auto u:graf[v]) dfs(u.fi,odl+(ll)u.se);
}
void dfs2(int v,int o,int odl){
if(odl>=naj1) naj1=odl,naj2=v;
oo[v]=odl;
for(auto u:graf[v]) {
if(u.fi==o) continue;
dfs2(u.fi,v,odl+(ll)u.se);
}
}
void dfs3(int v,int o,int odl){
oo[v]=max(oo[v],odl);
xdd=min(xdd,oo[v]);
for(auto u:graf[v]){
if(u.fi==o) continue;
dfs3(u.fi,v,odl+u.se);
}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for(int i=0;i<m;i++) a[i]++,b[i]++,graf[a[i]].push_back({b[i],t[i]}),graf[b[i]].push_back({a[i],t[i]});
vector<int>v;
int res=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
naj1=0,naj2=0;
dfs(i,0);
int g=naj2;
naj1=0;
dfs2(g,g,0);
res=max(res,naj1);
xdd=INT_MAX;
dfs3(naj2,naj2,0);
v.push_back(xdd);
}
}
sort(v.begin(),v.end(),[](int a,int b){
return a>b;
});
for(int i=1;i<=n;i++) vis[i]=0,oo[i]=0,graf[i].clear();
if(v.size()==2) return max(v[0]+l+v[1],res);
else{
if(v.size()==1) return max(res,v[0]);
else return max({v[0]+l+v[1],v[1]+l+l+v[2],res});
}
}