#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
vector< pair<int/*node*/,int/*distance*/> > adj[nmax];
bool been[nmax];
int dist[nmax];
int parent[nmax];
vector<int> active;
void dfs(int node,int par,int d)
{
if(been[node])return;
active.push_back(node);
parent[node]=par;
been[node]=1;
dist[node]=d;
for(auto k:adj[node])
dfs(k.first,node,k.second+d);
}
vector<int> comp;
bool cmp(int x,int y)
{
return x>y;
}
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]});
}
int O=0;
for(int i=0;i<N;i++)
if(been[i]==0)
{
active={};
dfs(i,0,0);
int where=i;
for(auto k:active)
if(dist[where]<dist[k])where=k;
for(auto k:active)
{
been[k]=0;
dist[k]=0;
}
active={};
dfs(where,0,0);
int other=where;
for(auto k:active)
if(dist[other]<dist[k])other=k;
/*
cout<<i<<" -> "<<where<<" "<<other<<" "<<dist[other]<<endl;
cout<<"active: ";for(auto k:active)cout<<k<<" ";cout<<endl;
cout<<"parent: ";for(int i=1;i<=N;i++)cout<<parent[i]<<" ";cout<<endl;
*/
int ans=dist[other],f=0,total=dist[other];
O=max(O,ans);
int run=other;
while(other!=where)
{
for(auto k:adj[other])
if(k.first==parent[other])f=f+k.second;
other=parent[other];
if(max(f,total-f)<ans)run=other;
ans=min(ans,max(f,total-f));
}
//cout<<i<<" -> "<<ans<<" "<<run<<endl;
for(auto k:active)
been[k]=0;
active={};
dfs(run,0,0);
//for(auto k:active)cout<<k<<" -> "<<dist[k]<<endl;
for(auto k:active)
assert(dist[k]<=ans);
comp.push_back(ans);
//cout<<i<<" -> "<<ans<<endl;
}
sort(comp.begin(),comp.end(),cmp);
if(comp.size()==1)return max(O,comp[0]);
if(comp.size()==2)return max(comp[0]+L+comp[1],O);
return max(O,max(comp[0]+L+comp[1],comp[1]+L+L+comp[2]));
}
/*
const int N=12,M=8,L=2;
int a[M]={0, 8, 2, 5, 5, 1, 1, 10};
int b[M]={8, 2, 7, 11, 1, 3, 9, 6};
int t[M]={4, 2, 4, 3, 7, 1, 5, 3};
int main()
{
cout<<travelTime(N,M,L,a,b,t)<<endl;
}
*/
Compilation message
/tmp/ccBXAIWd.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
