#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define en '\n'
#define sp ' '
typedef long long ll;
#define pii pair<int,int>
const int N=1e5+10;
vector<pii> adj[N];
set<int,greater<int>>s;
vector<int> st;
int target,start;
vector<int> qs(N),par(N);
vector<int> vis(N);
int mx,mxn,node;
void dfs1(int u,int p,int nw){
vis[u]=1;
// cout << u << sp;
if(mxn<nw){
mxn=nw;
node=u;
}
for(auto [v,w]:adj[u]){
if(v==p)continue;
dfs1(v,u,nw+w);
}
return ;
}
void dfs2(int u,int p,int nw){
par[u]=p;
// cout << 's' << u << sp <<p << en;
if(mx<nw){
mx=nw;
target=u;
}
for(auto [v,w]:adj[u]){
if(v==p)continue;
dfs2(v,u,nw+w);
}
return;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0;i<m;i++){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
for(int i=0;i<m;i++)sort(adj[i].begin(),adj[i].end());
// cout << en;
for(int i=0;i<n;i++){
if(!vis[i]){
// cout << "i" << i << sp;
mx=0,mxn=0,node=i,target=i;
dfs1(i,-1,0);
// cout << en;
// cout << i << sp << mxn << sp << node << en;
start=node;
dfs2(start,-1,0);
int trav=target;
// for(int i=0;i<n;i++)cout << par[i] << sp;
// cout << en;
st.push_back(0);
while (par[trav]!=-1)
{
// cout << trav << sp;
st.push_back(lower_bound(adj[trav].begin(),adj[trav].end(),make_pair(par[trav],0))->second);
trav=par[trav];
}
// cout << trav;
// cout << en;
for(int i=1;i<st.size();i++){
st[i]+=st[i-1];
// cout << st[i] << sp;
}
// cout << en;
// cout << target << sp << qs[st.size()-1] << en;
int mi=1e9;
for(int i=0;i<st.size();i++){
mi=min(mi,max(st[i],st.back()-st[i]));
}
// cout << "mi " << mi << en;
// if(mi==1e9)s.insert(0);
// else s.insert(mi);
s.insert(mi);
st.clear();
// cout << en;
}
}
// for(int i:s)cout << i << sp;
// int f1=q.top();
// q.pop();
// int f2=q.top();
if(s.size()==1){
return *s.begin();
}
int f1=*s.begin(),f2=*next(s.begin());
return f1+f2+l;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |