#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dsuu
{
vector<int> par;
dsuu(int n)
{
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int u)
{
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool same(int u, int v)
{
return find(u) == find(v);
}
void unite(int u, int v)
{
u = find(u), v = find(v);
par[v] = u;
}
};
dsuu dsu(100000);
vector<pair<int,int>> g[100000];
int rep[100000];
bool vis[100000];
int par[100000];
int dist[100000];
pair<int,int> dfs(int u)
{
vis[u] = true;
pair<int,int> res = {0, u};
for (auto [v, t] : g[u])
if (!vis[v])
{
par[v] = u;
dist[v] = dist[u] + t;
pair<int,int> x = dfs(v);
x.first += t;
res = max(res, x);
}
return res;
}
int furthest(int u)
{
memset(vis, false, sizeof(vis));
par[u] = u;
dist[u] = 0;
return dfs(u).second;
}
int center(int u)
{
int x = furthest(u);
x = furthest(x);
int y = furthest(x);
int distmax = dist[y];
int res = y;
while (y != x)
{
y = par[y];
if (abs(dist[y]*2 - distmax) < abs(dist[res]*2 - distmax))
res = y;
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; i++)
{
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
dsu.unite(A[i], B[i]);
}
vector<pair<int,int>> centers;
for (int i = 0; i < N; i++)
if (dsu.find(i) == i)
{
int c = center(i);
int f = furthest(c);
centers.push_back({dist[f], c});
}
sort(centers.rbegin(), centers.rend());
int res = dist[furthest(furthest(centers[0].second))];
if (centers.size() >= 2)
res = max(res, centers[0].first + L + centers[1].first);
if (centers.size() >= 3)
res = max(res, centers[1].first + 2 * L + centers[2].first);
return res;
}
Compilation message
/usr/bin/ld: /tmp/ccL0DbEV.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
