#include<bits/stdc++.h>
//#include"dreaming.h"
#define f first
#define s second
#define ll long long
using namespace std;
const int N = 2e5 + 500;
typedef pair<int , int> ipair;
int n , m , L;
vector<ipair> adj[N];
int component[N];
int dpD[N] , dpU[N];
bool vis[N];
int cmp;
int MN[N] , mx1[N] , mx2[N];
vector<int> dist;
void dfsD(int u , int BOSS){
vis[u] = 1;
component[u] = cmp;
for(ipair x : adj[u]){
int v = x.f , w = x.s;
if(vis[v])continue;
dfsD(v , BOSS);
dpD[u] = max(dpD[u] , dpD[v] + w);
if(u == BOSS){
if(mx2[component[v]] < dpD[v] + w) mx2[component[v]] = dpD[v] + w;
if(mx2[component[v]] > mx1[component[v]]) swap(mx2[component[v]] , mx1[component[v]]);
}
}
}
void dfsU(int u , int BOSS){
vis[u] = 1;
for(ipair x : adj[u]){
int v = x.f , w = x.s;
if(vis[v]) continue;
if(u == BOSS){
if(dpD[v] + w == mx1[component[v]]){
if(mx2[component[v]] == -1){
dpU[v] = w;
} else
dpU[v] = mx2[component[v]] + w;
} else {
dpU[v] = mx1[component[v]] + w;
}
} else
dpU[v] = dpU[u] + w;
dfsU(v , BOSS);
}
}
int travelTime(int N , int M , int L , int A[] , int B[] , int C[]){
n = N; m = M; L = L;
for(int i = 0; i < m; ++i){
adj[A[i]].emplace_back(B[i] , C[i]);
adj[B[i]].emplace_back(A[i] , C[i]);
}
for(int i = 0; i < n; ++i){
mx1[cmp] = -1 , mx2[cmp] = -1;
if(!vis[i]) {dfsD(i , i); cmp++;};
}
for(int i = 0; i < n; ++i) vis[i] = 0;
for(int i = 0; i < n; ++i){
if(!vis[i]) dfsU(i , i);
}
/*
for(int i = 0; i < n; ++i){
cerr << i << " i : " << dpD[i] << " dpD " << " : " << " dpU " << dpU[i] << endl;
}
*/
///cerr << cmp - 1<< " CMP " << endl;
for(int i = 0; i < cmp; ++i) MN[i] = 1e18;
for(int i = 0; i < n; ++i){
MN[component[i]] = min(MN[component[i]] , max(dpD[i] , dpU[i]));
}
//for(int i = 0; i < cmp; ++i) cout << i << " cmp " << MN[i] << endl;
for(int i = 0; i < cmp; ++i){
dist.emplace_back(MN[i]);
} sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
return max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
/*
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> L;
for(int i = 0; i < m; ++i){
int u , v , w;
cin >> u >> v >> w;
adj[u].emplace_back(v , w);
adj[v].emplace_back(u , w);
}
for(int i = 0; i < n; ++i){
mx1[cmp] = -1 , mx2[cmp] = -1;
if(!vis[i]) {dfsD(i , i); cmp++;};
}
for(int i = 0; i < n; ++i) vis[i] = 0;
for(int i = 0; i < n; ++i){
if(!vis[i]) dfsU(i , i);
}
for(int i = 0; i < n; ++i){
cerr << i << " i : " << dpD[i] << " dpD " << " : " << " dpU " << dpU[i] << endl;
}
///cerr << cmp - 1<< " CMP " << endl;
for(int i = 0; i < cmp; ++i) MN[i] = 1e18;
for(int i = 0; i < n; ++i){
MN[component[i]] = min(MN[component[i]] , max(dpD[i] , dpU[i]));
}
//for(int i = 0; i < cmp; ++i) cout << i << " cmp " << MN[i] << endl;
for(int i = 0; i < cmp; ++i){
dist.emplace_back(MN[i]);
} sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
cout << max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L) << endl;
return 0;
}
*/
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:77:42: warning: overflow in implicit constant conversion [-Woverflow]
for(int i = 0; i < cmp; ++i) MN[i] = 1e18;
^~~~
/tmp/cc3NQj1Z.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
