#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
int res = 0;
vector<ll>dist[2];
ll subtree[100005];
ll pos = 0;
vector<vector<ii> >adj;
ll maxi = 0;
ll node;
bool v[100005] = {0};
priority_queue<ii,vector<ii>,greater<ii> > pq;
void dfs(ll s,ll p,ll sum){
maxi = max(maxi,sum);
v[s] = 1;
subtree[s] = pos;
if(sum == maxi){
node = s;
}
for(auto x:adj[s]){
if(x.F != p){
dfs(x.F,s,sum+x.S);
}
}
}
void dijkstra(ll s,ll pos){
dist[pos][s] = 0;
pq.push(ii(0,s));
while(!pq.empty()){
ii f = pq.top();
pq.pop();
ll w,u;
w = f.F;
u = f.S;
if(w > dist[pos][u]){
continue;
}
for(auto x:adj[u]){
if(dist[pos][u] + 1 < dist[pos][x.F]){
dist[pos][x.F] = dist[pos][u] + x.S;
pq.push(ii(dist[pos][x.F],x.F));
}
}
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
adj.assign(n+5,vector<ii>());
f(i,0,m){
adj[A[i]].pb(ii(B[i],T[i]));
adj[B[i]].pb(ii(A[i],T[i]));
}
dist[0].assign(n+5,INF);
dist[1].assign(n+5,INF);
f(i,1,n+1){
if(v[i] == 0){
maxi = 0;
dfs(i,0,0);
ll u = node;
maxi = 0;
dfs(u,0,0);
dijkstra(u,0);
dijkstra(node,1);
pos++;
}
}
ll mini[pos];
f(i,0,pos){
mini[i] = 1e9+7;
}
f(i,1,n+1){
res = max({res,dist[0][i],dist[1][i]});
mini[subtree[i]] = min(mini[subtree[i]],max(dist[0][i],dist[1][i]));
}
sort(mini,mini+pos);
if(pos >= 2){
res = max(res,mini[pos-1] + mini[pos-2] + L);
}
if(pos >= 3){
res = max(res,mini[pos-3] + mini[pos-2] + 2 * L);
}
return res;
}
Compilation message
/usr/bin/ld: /tmp/ccKPAuXC.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
