//#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=2e18;
vector<pll> ed[100005];
ll dist[100005],n,m,maxx=0,vis[100005];
vector<ll> tmp,path;
void dfs(ll u,ll p)
{
tmp.pb(u);
for(auto v:ed[u])
{
if(v.F==p) continue;
dist[v.F]=dist[u]+v.S;
dfs(v.F,u);
}
}
bool findpath(ll u,ll p,ll d)
{
bool ret=0;
if(dist[u]==d) ret=1;
for(auto v:ed[u])
{
if(v.F==p) continue;
if(findpath(v.F,u,d)) ret=1;
}
if(ret) path.pb(dist[u]);
return ret;
}
ll findmid(ll st)
{
tmp.clear();
path.clear();
dfs(st,-1);
ll mx=-1,s=-1;
for(ll u:tmp)
{
if(mx<dist[u]) mx=dist[u],s=u;
dist[u]=0,vis[u]=1;
}
tmp.clear();
dfs(s,-1);
mx=-1;
ll t=-1;
for(ll u:tmp) if(mx<dist[u]) mx=dist[u],t=u;
maxx=max(maxx,mx);
findpath(s,-1,mx);
ll mn=INF;
for(ll u:path) mn=min(mn,max(mx-u,u));
//cout<<st<<" "<<mn<<"\n";
return mn;
}
int travelTime(int N,int M,int L,int A[], int B[], int T[])
{
n=N,m=M;
ll l=L;
vector<ll> ans;
rep(i,m)
{
ll u=A[i],v=B[i],w=T[i];
ed[u].pb({v,w});
ed[v].pb({u,w});
}
rep(i,n)
{
if(vis[i]) continue;
ans.pb(findmid(i));
}
sort(ans.begin(),ans.end(),greater<ll>());
if(ans.size()==1) return maxx;
else if(ans.size()==2) return max(maxx,ans[0]+ans[1]+l);
else return max({maxx,ans[0]+ans[1]+l,ans[1]+ans[2]+2*l});
}
Compilation message
dreaming.cpp: In function 'll findmid(ll)':
dreaming.cpp:51:8: warning: variable 't' set but not used [-Wunused-but-set-variable]
51 | ll t=-1;
| ^
/tmp/ccKyNUrj.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
