Submission #1207827

#TimeUsernameProblemLanguageResultExecution timeMemory
1207827orcslopDreaming (IOI13_dreaming)C++20
59 / 100
1096 ms9552 KiB
#include <bits/stdc++.h> #if __has_include("dreaming.h") #include "dreaming.h" #endif #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,tune=native") using namespace std; using ll = long long; #ifdef LOCAL #include "debug.h" #else #define dbg(...) 0 #define dbgn(...) 0 #endif const int INF = 1e9; // Assuming the function signature from the problem int travelTime(int n, int m, int l, int a[], int b[], int t[]) { vector<vector<pair<int, int>>> adj(n); 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]}); } const int INF = 1e9; vector<int> cc_radii; vector<int> cc_diameters; auto dijkstra = [&](int start_node) { vector<int> dist(n, INF); if (start_node >= 0 && start_node < n) { dist[start_node] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start_node}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; for (auto& edge : adj[u]) { int v = edge.first; int weight = edge.second; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } } return dist; }; vector<bool> vis(n, false); for (int i = 0; i < n; ++i) { if (!vis[i]) { vector<int> ccn; queue<int> q; q.push(i); vis[i] = true; while (!q.empty()) { int u = q.front(); q.pop(); ccn.push_back(u); for (auto& edge : adj[u]) { int v = edge.first; if (!vis[v]) { vis[v] = true; q.push(v); } } } if (ccn.size() <= 1) { cc_radii.push_back(0); cc_diameters.push_back(0); continue; } vector<int> st_dist = dijkstra(i); int endpoint_a = -1; int max_dist = -1; for (int node : ccn) { if (st_dist[node] != INF && st_dist[node] > max_dist) { max_dist = st_dist[node]; endpoint_a = node; } } vector<int> a_dist = dijkstra(endpoint_a); int endpoint_b = -1; int component_diameter = -1; for (int node : ccn) { if (a_dist[node] != INF && a_dist[node] > component_diameter) { component_diameter = a_dist[node]; endpoint_b = node; } } cc_diameters.push_back(component_diameter); vector<int> b_dist = dijkstra(endpoint_b); int component_radius = INF; for (int node : ccn) { int e = max(a_dist[node], b_dist[node]); if (e < component_radius) { component_radius = e; } } cc_radii.push_back(component_radius); } } int ans = 0; if (!cc_diameters.empty()) { ans = *max_element(cc_diameters.begin(), cc_diameters.end()); } sort(cc_radii.begin(), cc_radii.end(), greater<int>()); if (cc_radii.size() >= 2) { ans = max(ans, cc_radii[0] + cc_radii[1] + l); } if (cc_radii.size() >= 3) { ans = max(ans, cc_radii[1] + cc_radii[2] + 2 * l); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...