#include <bits/stdc++.h>
using namespace std;
const int maxN = (int) 1e5 + 1;
vector<vector<pair<int,int>>> adj;
int cnt = 0, n, m, l,sz = 0, ans = 0;
bool vis[maxN];
int parent[maxN];
vector<pair<int,int>> p;
void init(){
adj.resize(n);
p.resize(n);
memset(parent, -1, sizeof(parent));
}
pair<int, int> bfs(int node){
sz = 0;
bool seen[n];
int depth[n];
memset(seen, 0, sizeof(seen));
memset(depth, 0, sizeof(depth));
int best_node = node, best_dist = 0;
depth[node] = 0;
seen[node] = true; vis[node] = true;
queue<int> qs;
qs.emplace(node);
while(!qs.empty()){
auto f = qs.front();
sz++;
if(depth[f] > best_dist){
best_dist = depth[f];
best_node = f;
}
qs.pop();
for(auto x : adj[f]){
if(seen[x.first]) continue;
vis[x.first] = true;
qs.emplace(x.first);
parent[x.first] = f;
depth[x.first] = x.second + depth[f];
seen[x.first] = true;
}
}
return make_pair(best_node, best_dist);
}
int Get_total(int node){
auto val = bfs(node);
auto f = bfs(val.first);
return f.second;
}
void Do(int node){
auto val = bfs(node);
if(sz == 1) {
p[cnt++] = make_pair(0, node);
return ;
}
auto Tke = bfs(val.first);
parent[val.first] = -1;
int cur = Tke.first;
vector<int> path, len;
while(cur != -1){
int nxt = parent[cur];
path.emplace_back(cur);
if(nxt == -1) break;
auto q = lower_bound(adj[cur].begin(),adj[cur].end(), make_pair(nxt, 0));
len.emplace_back((*q).second);
cur = parent[cur];
}
int Max = (int)1e9, best_node = -1, s = 0;
for(int i = 0; i < (int)path.size(); i++){
if(i > 0) s += len[i - 1];
int now_max = max(s, Tke.second - s);
if(now_max < Max){
Max = now_max;
best_node = path[i];
}
}
ans = max(ans, Tke.second);
assert(best_node != -1);
p[cnt++] = make_pair(Max, best_node);
return ;
}
void make(){
for(int i = 0; i < n; i++){
if(vis[i]) continue;
Do(i);
vis[i] = true;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
l = L;
init();
for (int i = 0; i < m; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 0; i < n; i++){
sort(adj[i].begin(),adj[i].end());
}
make();
sort(p.rbegin(),p.rend());
if(cnt >= 2) {
ans = max(ans, p[0].first + p[1].first + l);
}
if(cnt >= 3) {
ans = max(ans, p[1].first + p[2].first + 2 * l);
}
return ans;
}
Compilation message
/usr/bin/ld: /tmp/cc9Qpuci.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
