Submission #1262060

#TimeUsernameProblemLanguageResultExecution timeMemory
1262060ciao_gio꿈 (IOI13_dreaming)C++20
47 / 100
73 ms9032 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { vector<vector<array<int, 2>>> 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]}); } vector<int> d0(N, 1e9), d1(N, 1e9), d2(N, 1e9); vector<bool> v0(N, false), v1(N, false), v2(N, false), vf(N, false); auto dijkstra = [N, &adj] (int i, vector<int> &distance, vector<bool> &visited) -> int { priority_queue<array<int, 2>> q; q.push({0, i}); distance[i] = 0; int x = i; while (!q.empty()) { auto [_, v] = q.top(); q.pop(); if (visited[v]) continue; if (distance[v] > distance[x]) x = v; visited[v] = true; for (auto [u, w]: adj[v]) { if (distance[v] + w < distance[u]) { distance[u] = distance[v] + w; q.push({-distance[u], u}); } } } return x; }; auto find_center = [N, &adj, &d1, &d2, &vf] (int i) -> int { queue<int> q; vf[i] = true; q.push(i); int x = i; while(!q.empty()) { int v = q.front(); q.pop(); for (auto [u, _]: adj[v]) { if (vf[u]) continue; if (max(d1[u], d2[u]) < max(d1[x], d2[x])) x = u; vf[u] = true; q.push(u); } } return x; }; int res = 0; int e1 = 0, e2 = -L; for (int i = 0; i < N; i++) { if (vf[i]) continue; int a = dijkstra(i, d0, v0); int b = dijkstra(a, d1, v1); dijkstra(b, d2, v2); res = max(res, d1[b]); int c = find_center(i); int e = max(d1[c], d2[c]); if (e > e1) { e2 = e1; e1 = e; } else if (e > e2) { e2 = e; } } res = max(res, e1 + e2 + L); return res; }
#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...