제출 #483977

#제출 시각아이디문제언어결과실행 시간메모리
483977arujbansal경주 (Race) (IOI11_race)C++17
31 / 100
191 ms42692 KiB
#include "race.h" #include <iostream> #include <vector> using namespace std; const int MXN = 2e5 + 1, INF = 1e9 + 5; vector<pair<int, int>> g[MXN]; int subtree_sz[MXN]; bool vis[MXN]; int N, K; int ans = INF; struct two_set { pair<int, int> x, y; two_set() { x = y = make_pair(INF, INF); } void insert(int val, int node) { if (val < y.first) y = make_pair(val, node); if (x.first > y.first) swap(x, y); } int query(int exclude_node) { if (x.second == exclude_node) return y.first; return x.first; } void work(int u) { if (x.second == u) x = make_pair(INF, INF); else if (y.second == u) y = make_pair(INF, INF); if (x.first > y.first) swap(x, y); } } mn_val[int(1e6) + 5]; int find_centroid(int u, int p, int nodes) { if (p != -1) { subtree_sz[p] -= subtree_sz[u]; subtree_sz[u] += subtree_sz[p]; } for (const auto &[v, wt] : g[u]) if (v != p && !vis[v] && subtree_sz[v] * 2 > nodes) return find_centroid(v, u, nodes); return u; } vector<int> to_reset; void calc_dist(int u, int p, int len, int depth, bool remove) { if (!remove) { if (len <= K) mn_val[len].insert(depth, u); to_reset.push_back(len); } else { if (len <= K) { mn_val[len].work(u); } } if (len > K) return; for (const auto &[v, wt] : g[u]) if (v != p && !vis[v]) calc_dist(v, u, len + wt, depth + 1, remove); } void calc_ans(int u, int p, int len, int depth) { if (len < K) ans = min(ans, depth + mn_val[K - len].query(u)); if (len == K) ans = min(ans, depth); if (len > K) return; for (const auto &[v, wt] : g[u]) if (v != p && !vis[v]) calc_ans(v, u, len + wt, depth + 1); } void calc_sz(int u, int p) { subtree_sz[u] = 1; for (const auto &[v, wt] : g[u]) { if (v == p) continue; calc_sz(v, u); subtree_sz[u] += subtree_sz[v]; } } void cd(int u) { int centroid = find_centroid(u, -1, subtree_sz[u]); vis[centroid] = true; for (const auto &[v, wt] : g[centroid]) if (!vis[v]) calc_dist(v, centroid, wt, 1, false); for (const auto &[v, wt] : g[centroid]) { if (!vis[v]) { calc_dist(v, centroid, wt, 1, true); calc_ans(v, centroid, wt, 1); calc_dist(v, centroid, wt, 1, false); } } for (const auto &x : to_reset) mn_val[x] = two_set(); to_reset.clear(); for (const auto &[v, wt] : g[centroid]) if (!vis[v]) cd(v); } int best_path(int _N, int _K, int _H[][2], int _L[]) { N = _N, K = _K; for (int i = 0; i < N - 1; i++) { _H[i][0]++; _H[i][1]++; g[_H[i][0]].emplace_back(_H[i][1], _L[i]); g[_H[i][1]].emplace_back(_H[i][0], _L[i]); } calc_sz(1, -1); cd(1); return (ans < INF ? ans : -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...