// #include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const long long N=1e5+200;
vector<pair<long long,long long>> ma[N];
bool vis[N];
bool tp=0;
long long dp_down[N][2];
long long dp_up[N];
long long mxx[N];
long long n,m,l;
void dfs_down(long long x,long long p=-1)
{
vis[x]=1;
dp_down[x][0]=dp_down[x][1]=0;
for(auto [w,y]:ma[x])
{
if(y!=p)
{
dfs_down(y,x);
long long cur=dp_down[y][0]+w;
if(dp_down[x][0]<cur)
{
dp_down[x][1]=dp_down[x][0];
dp_down[x][0]=cur;
}
else if(dp_down[x][1]<cur)
{
dp_down[x][1]=cur;
}
}
}
}
long long vertex=-1;
long long dist=1e18;
long long cp=-1;
void fill()
{
for(int i=0;i<n;i++)
dp_up[i]=0;
}
void dfs_up(long long x,long long p=-1)
{
mxx[x]=max(dp_up[x],dp_down[x][0]);
cp=max(cp,mxx[x]);
if(mxx[x]<dist)
{
dist=mxx[x];
vertex=x;
}
for(auto [w,y]:ma[x])
{
if(y!=p)
{
dp_up[y]=dp_up[x]+w;
if(dp_down[x][0]==(dp_down[y][0]+w))
dp_up[y]=max(dp_up[y],dp_down[x][1]+w);
else
dp_up[y]=max(dp_up[y],dp_down[x][0]+w);
dfs_up(y,x);
}
}
}
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++)
{
ma[a[i]].push_back({t[i],b[i]});
ma[b[i]].push_back({t[i],a[i]});
}
set<pair<long long,long long>> stp;
for(int i=0;i<n;i++)
{
if(!vis[i]){
vertex=-1;
dist=1e18;
dfs_down(i);
dfs_up(i);
stp.insert({dist,vertex});
}
}
while(stp.size()>1)
{
auto lt=*(--end(stp));
stp.erase((--end(stp)));
auto ft=*(begin(stp));
stp.erase((begin(stp)));
// Merge them
ma[lt.second].push_back({l,ft.second});
ma[ft.second].push_back({l,lt.second});
vertex=lt.second;
dist=max(ft.first+l,lt.first);
// dfs_down(lt.second);
// fill();
// dfs_up(lt.second);
stp.insert({dist,vertex});
}
cp=-1;
tp=1;
dfs_down(0);
fill();
dfs_up(0);
// cout<<"adj\n";
// for(int i=0;i<n;i++)
// {
// cout<<"For "<<i<<' ';
// for(auto [j,p]:ma[i]){
// cout<<p<<' ';
// }
// cout<<endl;
// cout<<"a\n";
// }
return cp;
}
Compilation message
/usr/bin/ld: /tmp/cc4wFYqw.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
