제출 #422788

#제출 시각아이디문제언어결과실행 시간메모리
422788SuhaibSawalha1경주 (Race) (IOI11_race)C++17
0 / 100
1 ms204 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; vector<vector<array<int, 2>>> adj; int n, k, ans = 2e9, nodes; vector<int> sub; bitset<200000> is_cent; map<int, int> mp2; void precalc (int u, int p = -1) { sub[u] = 1; ++nodes; for (auto &v : adj[u]) { if (!is_cent[v[0]] && v[0] ^ p) { precalc(v[0], u); sub[u] += sub[v[0]]; } } } int centroid (int u, int p = -1) { bool is = nodes - sub[u] <= nodes / 2; int heavy = -1; for (auto &v : adj[u]) { if (!is_cent[v[0]] && v[0] ^ p) { is &= sub[v[0]] <= nodes / 2; if (heavy == -1 || sub[heavy] < sub[v[0]]) { heavy = v[0]; } } } return is ? u : centroid(heavy, u); } void update (map<int, int> &m, int k, int v) { if (m.count(k)) { m[k] = min(m[k], v); } else { m[k] = v; } } void dfs (int u, int p, int sum, int d) { if (sum > k) { return; } update(mp2, sum, d); for (auto &v : adj[u]) { if (!is_cent[v[0]] && v[0] ^ p) { dfs(v[0], u, sum + v[1], d + 1); } } } void decompose (int u = 0) { nodes = 0; precalc(u); int cent = centroid(u); map<int, int> mp; mp[0] = 0; is_cent[cent] = 1; for (auto &v : adj[cent]) { if (is_cent[v[0]]) { continue; } mp2.clear(); dfs(v[0], u, v[1], 1); for (auto &p : mp2) { if (mp.count(k - p.first)) { ans = min(ans, p.second + mp[k - p.first]); } } for (auto &p : mp2) { update(mp, p.first, p.second); } } for (auto &v : adj[cent]) { if (!is_cent[v[0]]) { decompose(v[0]); } } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; adj.resize(n); sub.resize(n); for (int i = 0; i < n - 1; ++i) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } decompose(); return ans == 2e9 ? -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...