제출 #362328

#제출 시각아이디문제언어결과실행 시간메모리
362328WLZ경주 (Race) (IOI11_race)C++14
0 / 100
1 ms364 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; class centroid_decomposition { private: int n, r; vector< vector<int> > g, cd; vector<int> sz; vector<bool> used; void build() { n = (int) g.size(); cd.resize(n); sz.resize(n); used.assign(n, false); dfs(0, -1); } void get_sizes(int u, int p) { sz[u] = 1; for (auto& v : g[u]) { if (!used[v] && v != p) { get_sizes(v, u); sz[u] += sz[v]; } } } int find_centroid(int u, int p, int n) { for (auto& v : g[u]) if (!used[v] && v != p && sz[v] > n / 2) return find_centroid(v, u, n); return u; } void dfs(int u, int p) { get_sizes(u, p); int n = sz[u]; int centroid = find_centroid(u, p, n); if (p != -1) cd[p].push_back(centroid); else r = centroid; used[centroid] = true; for (auto& v : g[centroid]) { if (!used[v] && v != p) { dfs(v, centroid); } } } public: centroid_decomposition() {} centroid_decomposition(const vector< vector<int> > &_g) : g(_g) { build(); } centroid_decomposition(const vector< vector< pair<int, int> > > &_g) { for (auto& u : _g) { g.push_back({}); for (auto& p : u) g.back().push_back(p.first); } build(); } const vector<int> &operator[](const int &u) { return cd[u]; } int root() { return r; } }; int n, k, max_log, dfs_cnt = 0; vector< vector< pair<int, int> > > g; vector< vector<int> > up; vector<int> dfs_in, dfs_out, cnt; vector<long long> d; void dfs(int u, int p) { up[u][0] = p; dfs_in[u] = dfs_cnt++; for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1]; for (auto& v : g[u]) { if (v.first != p) { cnt[v.first] = cnt[u] + 1; d[v.first] = d[u] + v.second; dfs(v.first, u); } } dfs_out[u] = dfs_cnt++; } bool is_anc(int u, int v) { return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u]; } int lca(int u, int v) { if (is_anc(u, v)) return u; if (is_anc(v, u)) return v; for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i]; return up[u][0]; } centroid_decomposition cd; vector<int> order, st, en; int dfs(int u) { int ans = INF; st[u] = en[u] = (int) order.size(); order.push_back(u); for (auto &v : cd[u]) { ans = min(ans, dfs(v)); en[u] = en[v]; } map<int, int> mp; mp[0] = 0; for (int i = st[u]; i <= en[u]; i++) { long long dist = d[u] + d[order[i]] - 2 * d[lca(u, order[i])]; int edges = cnt[u] + cnt[order[i]] - 2 * cnt[lca(u, order[i])]; if (mp.count(k - dist)) ans = min(ans, mp[k - dist] + edges); if (mp.count(dist)) mp[dist] = min(mp[dist], edges); else mp[dist] = edges; } return ans; } int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; g.resize(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]}); } max_log = ceil(log2(n)); up.assign(n, vector<int>(max_log + 1)); dfs_in.resize(n); dfs_out.resize(n); d.resize(n); d[0] = 0; cnt.resize(n); cnt[0] = 0; dfs(0, 0); cd = centroid_decomposition(g); st.resize(n); en.resize(n); int ans = dfs(cd.root()); if (ans == INF) return -1; return 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...