#include <bits/stdc++.h>
#include "dreaming.h"
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
const int MAXN = 1e5 + 5, INF = 1e9 + 5;
using ll = long long;
vector<pair<int, int>> g[MAXN];
vector<pair<int, int>> bestComps;
bool vis[MAXN];
pair<int, int> leaf[2];
pair<int, int> optimalRoot;
int diameterDist[MAXN][2];
void diameter(int u, int p, int dist, int idx) {
vis[u] = true;
leaf[idx] = max(leaf[idx], make_pair(dist, u));
diameterDist[u][idx] = dist;
optimalRoot = min(optimalRoot, make_pair(max(diameterDist[u][0], diameterDist[u][1]), u));
for (const auto &[v, wt] : g[u]) {
if (v == p) continue;
dfs(v, u, dist + wt, idx);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
leaf[0] = leaf[1] = {-INF, -INF};
diameter(u, -1, 0, 0);
diameter(leaf[0].second, -1, 0, 1);
optimalRoot = {INF, i};
diameter(leaf[1].second, -1, 0, 0);
bestComps.emplace_back(optimalRoot.first, optimalRoot.second);
}
sort(bestComps.begin(), bestComps.end(), greater<>());
int best = bestComps.front().second;
for (int i = 1; i < int(bestComps.size()); i++) {
int v = bestComps[i].second;
g[best].emplace_back(v, L);
g[v].emplace_back(best, L);
}
leaf[0] = leaf[1] = {-INF, -INF};
diameter(0, -1, 0, 0);
diameter(leaf[0].second, -1, 0, 1);
return leaf[1].first;
}
Compilation message
dreaming.cpp: In function 'void diameter(int, int, int, int)':
dreaming.cpp:27:9: error: 'dfs' was not declared in this scope; did you mean 'ffs'?
27 | dfs(v, u, dist + wt, idx);
| ^~~
| ffs
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:42:18: error: 'u' was not declared in this scope
42 | diameter(u, -1, 0, 0);
| ^
