제출 #1206391

#제출 시각아이디문제언어결과실행 시간메모리
1206391Captain_GeorgiaRace (IOI11_race)C++20
100 / 100
623 ms37700 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; int best_path(int N, int K, int H[][2], int L[]) { vector<array<int, 2>> g[N]; for (int i = 0;i < N - 1;i ++) { g[H[i][0]].push_back({H[i][1], L[i]}); g[H[i][1]].push_back({H[i][0], L[i]}); } int res = 1e9 + 7, mx = 0; vector<int> used(N, 0), sub(N, 0), dist(MAXN, 0); function<void(int, int)> dfs_init = [&](int si, int pi) -> void { sub[si] = 1; for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) { dfs_init(ti, si); sub[si] += sub[ti]; } }; function<int(int, int, int)> get_centr = [&](int si, int pi, int sz) -> int { for (auto [ti, wi] : g[si]) if (used[ti] == 0 && ti != pi && sub[ti] * 2 >= sz) { return get_centr(ti, si, sz); } return si; }; function<void(int, int, int, int)> calc = [&](int si, int pi, int depth, int len) -> void { if (len > K) return; if (len == K) res = min(res, depth); mx = max(mx, len); if (dist[K - len] != 0) res = min(res, dist[K - len] + depth); for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) { calc(ti, si, depth + 1, len + wi); } }; function<void(int, int, int, int)> update = [&](int si, int pi, int depth, int len) -> void { if (len > K) return; if (dist[len] == 0) dist[len] = depth; else dist[len] = min(dist[len], depth); for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) { update(ti, si, depth + 1, len + wi); } }; function<void(int)> decompose = [&](int si) -> void { dfs_init(si, si); if (sub[si] == 1) return; int centr = get_centr(si, si, sub[si]); used[centr] = 1; mx = 0; for (auto [ti, wi] : g[centr]) if (used[ti] == 0) { calc(ti, centr, 1, wi); update(ti, centr, 1, wi); } for (int i = 0;i <= mx;i ++) dist[i] = 0; for (auto [ti, wi] : g[centr]) if (used[ti] == 0) { decompose(ti); } }; decompose(0); if (res == 1e9 + 7) return -1; 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...