제출 #451981

#제출 시각아이디문제언어결과실행 시간메모리
451981palilo경주 (Race) (IOI11_race)C++17
43 / 100
290 ms27120 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; namespace std { // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {} template <class... Args> decltype(auto) operator()(Args&&... args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template <class Fun> decltype(auto) y_combinator(Fun&& fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } }; // namespace std template <class T> bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); } template <class T> bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); } int best_path(int n, int k, int e[][2], int w[]) { vector<vector<pair<int, int>>> adj(n); for (int i = 0; i < n - 1; ++i) { adj[e[i][0]].emplace_back(w[i], e[i][1]); adj[e[i][1]].emplace_back(w[i], e[i][0]); } vector<pair<int, int>> dists; vector<int> sz(n), dist(n); vector<bool> erased(n); int s; auto dfs_sz = y_combinator([&](auto self, int u, int p) -> int { sz[u] = 1; for (const auto& [w, v] : adj[u]) { if (v != p && !erased[v]) { sz[u] += self(v, u); } } return sz[u]; }); auto dfs_ct = y_combinator([&](auto self, int u, int p) -> int { for (const auto& [w, v] : adj[u]) { if (v != p && !erased[v] && sz[v] > s / 2) { return self(v, u); } } return u; }); auto dfs = y_combinator([&](auto self, int u, int p, int edges) -> void { if (dist[u] > k) return; dists.emplace_back(dist[u], edges); for (const auto& [w, v] : adj[u]) { if (v != p && !erased[v]) { dist[v] = dist[u] + w; self(v, u, edges + 1); } } }); int ans = INT_MAX, tick = 0; vector<pair<int, int>> table(k); y_combinator([&](auto self, int u) -> void { s = dfs_sz(u, -1); u = dfs_ct(u, -1); erased[u] = true; --tick; for (const auto& [w, v] : adj[u]) { if (erased[v]) continue; dists.clear(); dist[v] = w; dfs(v, u, 1); for (const auto& [d1, e1] : dists) { if (d1 == k) { chmin(ans, e1); } else { const auto d2 = k - d1; if (table[d2].first == tick) { chmin(ans, e1 + table[d2].second); } } } for (const auto& [d, e] : dists) { chmin(table[d], pair(tick, e)); } } for (const auto& [w, v] : adj[u]) { if (!erased[v]) { self(v); } } })(0); return ans == INT_MAX ? -1 : 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...