// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, W;
const int maxn = 2e5 + 7;
const int oo = 1e9 + 7;
vector<pii> adj[maxn];
vector<int> ls; int res;
int h[maxn], D1[maxn], D2[maxn];
int mark[maxn], col[maxn], c;
vector<int> A[maxn];
void dfs(int v) {
mark[v] = 1; col[v] = c; A[c].pb(v);
for (auto f : adj[v]) {
int u = f.F, w = f.S;
if (!mark[u]) {
dfs(u);
}
}
}
void cal_dfs(int v, int p = -1) {
if (p == -1) h[v] = 0;
for (auto f : adj[v]) {
int u = f.F, w = f.S;
if (u == p) continue;
h[u] = h[v] + w;
cal_dfs(u, v);
}
}
int cal_dis(int c) {
int v = A[c][0];
cal_dfs(v);
int u1 = A[c][0];
for (int r : A[c]) {
if (h[r] > h[u1]) u1 = r;
}
cal_dfs(u1);
for (int r : A[c]) D1[r] = h[r];
int u2 = A[c][0];
for (int r : A[c]) {
if (h[r] > h[u2]) u2 = r;
}
cal_dfs(u2);
for (int r : A[c]) {
D2[r] = h[r];
res = max(res, h[r]);
}
int mn = oo;
for (int r : A[c]) {
mn = min(mn, max(D1[r], D2[r]));
}
return mn;
}
int travelTime(int Nx, int Mx, int Lx, int Ax[], int Bx[], int Tx[]) {
n = Nx; m = Mx; W = Lx;
for (int i = 0; i < m; i++) {
int u = Ax[i], v = Bx[i], w = Tx[i];
adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
}
res = 0;
for (int i = 0; i < n; i++) {
if (!mark[i]) {
dfs(i);
ls.pb(cal_dis(c)); c++;
}
}
sort(all(ls), greater<int>());
if (len(ls) >= 2) res = max(res, ls[0] + ls[1] + W);
if (len(ls) >= 3) res = max(res, ls[1] + ls[2] + 2 * W);
return res;
}
Compilation message
dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:37:16: warning: unused variable 'w' [-Wunused-variable]
37 | int u = f.F, w = f.S;
| ^
/usr/bin/ld: /tmp/ccbGhPx2.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
