Submission #768488

#TimeUsernameProblemLanguageResultExecution timeMemory
768488boris_mihovDreaming (IOI13_dreaming)C++17
100 / 100
62 ms17564 KiB
#include "dreaming.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 100000 + 10; const int INF = 1e9; int n, m; int dp[MAXN]; int dp2[MAXN]; int next[MAXN]; bool vis[MAXN]; std::vector <std::pair <int,int>> g[MAXN]; std::vector <int> dists; void dfsDown(int node, int p) { dp[node] = dp2[node] = 0; for (const auto &[u, d] : g[node]) { if (u == p) { continue; } dfsDown(u, node); if (dp[u] + d > dp[node]) { dp2[node] = dp[node]; dp[node] = dp[u] + d; next[node] = u; } else if (dp[u] + d > dp2[node]) { dp2[node] = dp[u] + d; } } } int ans; int dfsUp(int node, int p, int edge) { vis[node] = true; if (p != 0) { if (next[p] != node) { if (dp[p] + edge > dp[node]) { dp2[node] = dp[node]; dp[node] = dp[p] + edge; next[node] = p; } else if (dp[p] + edge > dp2[node]) { dp2[node] = dp[p] + edge; } } else { if (dp2[p] + edge > dp[node]) { dp2[node] = dp[node]; dp[node] = dp2[p] + edge; next[node] = p; } else if (dp2[p] + edge > dp2[node]) { dp2[node] = dp2[p] + edge; } } } ans = std::max(ans, dp[node] + dp2[node]); int res = dp[node]; for (const auto &[u, d] : g[node]) { if (u != p) { res = std::min(res, dfsUp(u, node, d)); } } return res; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; m = M; for (int i = 0 ; i < m ; ++i) { g[A[i] + 1].push_back({B[i] + 1, T[i]}); g[B[i] + 1].push_back({A[i] + 1, T[i]}); } for (int i = 1 ; i <= n ; ++i) { if (vis[i]) { continue; } assert(dp[i] == 0); dfsDown(i, 0); dists.push_back(dfsUp(i, 0, 0)); } std::sort(dists.begin(), dists.end()); if (dists.size() == 1) return ans; ans = std::max(ans, dists[dists.size() - 2] + dists[dists.size() - 1] + L); if (dists.size() >= 3) ans = std::max(ans, dists[dists.size() - 3] + dists[dists.size() - 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...