Submission #944089

#TimeUsernameProblemLanguageResultExecution timeMemory
944089wiiDreaming (IOI13_dreaming)C++17
100 / 100
81 ms32284 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x).size() const int MaxN = 1e5 + 5; template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; } template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; } const int Inf = 0x3f3f3f3f; int n, m, l; vector<int> pref[MaxN], suff[MaxN]; vector<pair<int, int>> adj[MaxN]; int vis[MaxN]; int dep[MaxN], dp[MaxN]; void dfs(int u, int p) { vis[u] = true; for (auto [v, w]: adj[u]) if (v != p) { dep[v] = dep[u] + w; dfs(v, u); maximize(dp[u], dp[v] + w); } } int ans, diameter; void reroot(int u, int p) { minimize(ans, dp[u]); maximize(diameter, dp[u]); for (int i = 0; i < sz(adj[u]); ++i) { auto [v, w] = adj[u][i]; pref[u].emplace_back(dp[v] + w); suff[u].emplace_back(dp[v] + w); } for (int i = 0; i < sz(adj[u]); ++i) { auto [v, w] = adj[u][i]; if (i) maximize(pref[u][i], pref[u][i - 1]); } for (int i = sz(adj[u]) - 1; i >= 0; --i) { auto [v, w] = adj[u][i]; if (i + 1 < sz(adj[u])) maximize(suff[u][i], suff[u][i + 1]); } for (int i = 0; i < sz(adj[u]); ++i) { auto [v, w] = adj[u][i]; if (v == p) continue; int old = dp[v]; int nw = max((i ? pref[u][i - 1] : 0), (i + 1 < sz(adj[u]) ? suff[u][i + 1] : 0)); dp[u] = nw; dp[v] = max(dp[u] + w, old); reroot(v, u); dp[u] = pref[u].back(); dp[v] = old; } } int used[MaxN]; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; m = M; l = L; for (int i = 0; i < m; ++i) { int u = A[i]; int v = B[i]; int w = T[i]; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } vector<int> best; if (1) for (int i = 0; i < n; ++i) if (!vis[i]) { dfs(i, i); ans = Inf; reroot(i, i); best.push_back(ans); } sort(best.begin(), best.end(), greater<int>()); int maxD = 0; maximize(maxD, best[0]); if (best.size() >= 2) maximize(maxD, best[0] + best[1] + l); if (best.size() >= 3) maximize(maxD, best[1] + best[2] + 2*l); return max(maxD, diameter); }

Compilation message (stderr)

dreaming.cpp: In function 'void reroot(int, int)':
dreaming.cpp:42:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   42 |         auto [v, w] = adj[u][i];
      |              ^~~~~~
dreaming.cpp:47:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   47 |         auto [v, w] = adj[u][i];
      |              ^~~~~~
#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...