#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 7;
int val,ve;
bool used[maxN];
vector<pair<int, int>> v[maxN];
void dfs(int x, int p, int sum)
{
used[x] = true;
if(sum > val){
val = sum;
ve = x;
}
for(auto y : v[x]){
if(y.first != p){
dfs(y.first, x, sum + y.second);
}
}
}
int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T)
{
for(int i = 0; i < M; i++){
v[A[i]].push_back({B[i], T[i]});
v[B[i]].push_back({A[i], T[i]});
}
vector<int> p(N, -1);
vector<int> d(N, 1e9);
vector<pair<int, int>> X;
for(int i = 0; i < N; i++){
if(!used[i]){
val = ve = 0;
dfs(i, i, 0);
int r1 = ve;
val = ve = 0;
dfs(ve, ve, 0);
int r2 = ve;
int di = val;
queue<int> q;
q.push(r1);
d[r1] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto y : v[x]){
if(d[y.first] == 1e9){
d[y.first] = d[x] + 1;
p[y.first] = x;
q.push(y.first);
}
}
}
vector<int> pa;
while(r2 != r1){
pa.push_back(r2);
r2 = p[r2];
}
pa.push_back(r1);
int v1 = 0;
int res = 1e9;
for(int j = max(0, (int)pa.size() / 2 - 10); j < min((int)pa.size(), (int)pa.size() / 2 + 10); j++){
int st = pa[j];
queue<int> q;
q.push(st);
map<int, int> d;
int mx = 0;
d[st] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto y : v[x]){
if(d.find(y.first) == d.end()){
d[y.first] = d[x] + y.second;
q.push(y.first);
mx = max(mx, d[x] + y.second);
}
}
}
if(mx < res){
res = mx;
v1 = st;
}
}
X.push_back({res, v1});
}
}
sort(X.rbegin(), X.rend());
for(int i = 1; i < (int)X.size(); i++){
v[X[0].first].push_back({X[i].first, L});
v[X[i].first].push_back({X[0].first, L});
}
val = ve = 0;
dfs(0, 0, 0);
val = 0;
dfs(ve, ve, 0);
return val;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:43:29: warning: unused variable 'di' [-Wunused-variable]
43 | int di = val;
| ^~
/usr/bin/ld: /tmp/cc2nvF6d.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
