제출 #699980

#제출 시각아이디문제언어결과실행 시간메모리
699980elkernos경주 (Race) (IOI11_race)C++17
0 / 100
1 ms340 KiB
#include "race.h" #include "bits/stdc++.h" using namespace std; #define ssize(x) (int)size(x) template <class A, class B> auto &operator<<(ostream &o, pair<A, B> p) { return o << '(' << p.first << ", " << p.second << ')'; } template <class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) { o << '{'; int i = 0; for (auto e : x) o << (", ") + 2 * !i++ << e; return o << '}'; } #ifdef DEBUG #define debug(x...) cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x), cerr << '\n' #else #define debug(...) \ { \ } #endif int best_path(int N, int K, int H[][2], int L[]) { vector<vector<pair<int, int>>> graf(N); for (int i = 0; i < N; i++) { int a = H[i][0], b = H[i][1], c = L[i]; graf[a].push_back({b, c}); graf[b].push_back({a, c}); } const int oo = 1e9 + 2133; int ans = oo; vector<int> subsz(N); vector<bool> used(N); function<void(int, int)> calc_sz = [&](int u, int p) { subsz[u] = 1; for (auto [to, _] : graf[u]) { if (to == p || used[to]) continue; calc_sz(to, u); subsz[u] += subsz[to]; } }; function<int(int, int, int)> calc_centro = [&](int u, int p, int need) { for (auto [to, _] : graf[u]) { if (to == p || used[to]) continue; if (subsz[to] > need / 2) return calc_centro(to, u, need); } return u; }; vector<vector<pair<int, int>>> wek(K + 1); vector<int> cos; int pid = 0; function<void(int, int, int, int, int)> gather = [&](int u, int p, int len, int path_id, int edges_count) { if (len <= K) { wek[len].push_back({edges_count, path_id}); cos.push_back(len); } for (auto [to, tlen] : graf[u]) { if (to == p || used[to]) continue; gather(to, u, len + tlen, path_id, edges_count + 1); } }; function<void(int)> rek = [&](int u) { calc_sz(u, u); u = calc_centro(u, u, subsz[u]); for (auto [to, tlen] : graf[u]) { if (used[to]) continue; gather(to, u, tlen, ++pid, 1); } sort(cos.begin(), cos.end()); cos.erase(unique(cos.begin(), cos.end()), cos.end()); for (auto x : cos) { pair<int, int> min_1(N, 0), min_2(N, 0); for (auto d : wek[x]) { if (min_1 > d) { min_2 = min_1; min_1 = d; } else if (min_2 > d) min_2 = d; } for (auto d : wek[K - x]) { if (d.second != min_1.second) ans = min(ans, d.first + min_1.first); if (d.second != min_2.second) ans = min(ans, d.first + min_2.first); } } used[u] = 1; for (auto x : cos) { wek[x].clear(); } cos.clear(); for (auto [to, _] : graf[u]) { if (used[to]) continue; rek(to); } }; rek(1); return (ans >= N ? -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...