#include <vector> #include <algorithm> #include "dreaming.h" using namespace std; const int MAXN = 100005; vector<pair<int, int>> adj[MAXN]; bool visited[MAXN]; int max_d, farthest_node; int parent_node[MAXN], edge_to_parent[MAXN]; // Standard DFS to find the farthest node and distances void dfs(int u, int p, int d) { visited[u] = true; parent_node[u] = p; if (d > max_d) { max_d = d; farthest_node = u; } for (auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (v != p) { edge_to_parent[v] = w; dfs(v, u, d + w); } } } int get_min_max_dist(int start_node, int& component_diameter) { max_d = -1; dfs(start_node, -1, 0); int u = farthest_node; max_d = -1; dfs(u, -1, 0); int v = farthest_node; component_diameter = max_d; // Path from v back to u to find the center int curr = v; int dist_from_v = 0; int min_max_d = max_d; // Start with diameter while (curr != -1) { // The distance to the farthest end is max(dist_from_v, diameter - dist_from_v) min_max_d = min(min_max_d, max(dist_from_v, max_d - dist_from_v)); if (curr == u) break; dist_from_v += edge_to_parent[curr]; curr = parent_node[curr]; } return min_max_d; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; i++) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } vector<int> radii; int overall_max_diameter = 0; for (int i = 0; i < N; i++) { if (!visited[i]) { int comp_diam = 0; radii.push_back(get_min_max_dist(i, comp_diam)); overall_max_diameter = max(overall_max_diameter, comp_diam); } } sort(radii.rbegin(), radii.rend()); // Case with 2 components (Subtask 3) if (radii.size() >= 2) { overall_max_diameter = max(overall_max_diameter, radii[0] + radii[1] + L); } // Case with 3 or more components (General case) if (radii.size() >= 3) { overall_max_diameter = max(overall_max_diameter, radii[1] + radii[2] + 2 * L); } return overall_max_diameter; }