#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<pii>> gr;
vector<ll> std1,std2,mxd,rads;
vector<int> stdi,currt;
vector<bool> vis;
void dfs1(int u,int p) {
currt.push_back(u);
for(int i=0;i<gr[u].size();++i) {
int v=gr[u][i].first,d=gr[u][i].second;
if(v==p) continue;
dfs1(v,u);
if(std1[v]+d>std2[u]) std2[u]=std1[v]+d;
if(std1[v]+d>=std1[u]) {
std2[u]=std1[u];
std1[u]=std1[v]+d;
stdi[u]=i;
}
}
}
void dfs2(int u,int p,ll pd) {
mxd[u]=max(std1[u],pd);
for(int i=0;i<gr[u].size();++i) {
int v=gr[u][i].first,d=gr[u][i].second;
if(v==p) continue;
if(stdi[u]==i) dfs2(v,u,max(pd,std2[u])+d);
else dfs2(v,u,max(pd,std1[u])+d);
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
gr.resize(N);std1.resize(N,0);std2.resize(N,0);stdi.resize(N);vis.resize(N,0);mxd.resize(N,0);
for(int i=0;i<M;++i) {
gr[A[i]].push_back({B[i],T[i]});
gr[B[i]].push_back({A[i],T[i]});
}
ll mxdia=0;
for(int u=0;u<N;++u) {
if(!vis[u]) {
dfs1(u,-1);
dfs2(u,-1,0);
ll rad=LLONG_MAX;
for(int v:currt) {
vis[v]=1;
rad=min(rad,mxd[v]);
mxdia=max(mxdia,mxd[v]);
}
rads.push_back(rad);
currt.clear();
}
}
sort(rads.rbegin(),rads.rend());
return max({mxdia,rads.size()>1?rads[0]+L+rads[1]:0,rads.size()>2?rads[1]+L+L+rads[2]:0});
}
Compilation message
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<gr[u].size();++i) {
| ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, ll)':
dreaming.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=0;i<gr[u].size();++i) {
| ~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccPY4ehJ.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
