제출 #922007

#제출 시각아이디문제언어결과실행 시간메모리
922007Beerus13경주 (Race) (IOI11_race)C++17
100 / 100
259 ms40900 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> const int N = 2e5 + 5; const int K = 1e6 + 5; const int inf = 1e9; int n, k; int dp[K], val[N], dep[N], cnt[N], sz[N]; bool del[N]; vector<pii> g[N]; vector<int> node, tree; int ans = inf; int dfs_size(int u, int p = 0) { sz[u] = 1; for(auto [v, _] : g[u]) if(v != p && !del[v]) sz[u] += dfs_size(v, u); return sz[u]; } int find_centroid(int u, int p, int num) { for(auto [v, _] : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num); return u; } void dfs_centroid(int u, int p) { if(val[u] > k) return; dep[u] = dep[p] + 1; node.push_back(u); tree.push_back(u); ans = min(ans, dep[u] + dp[k - val[u]]); for(auto [v, w] : g[u]) if(v != p && !del[v]) { val[v] = val[u] + w; dfs_centroid(v, u); } } void decomposition(int u) { int centroid = find_centroid(u, 0, dfs_size(u)); del[centroid] = 1; dep[centroid] = val[centroid] = dp[0] = 0; tree.push_back(centroid); for(auto [v, w] : g[centroid]) if(!del[v]) { val[v] = w; dfs_centroid(v, centroid); for(int x : node) dp[val[x]] = min(dp[val[x]], dep[x]); node.clear(); } for(int x : tree) dp[val[x]] = inf; tree.clear(); for(auto [v, _] : g[centroid]) if(!del[v]) { decomposition(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) { int u = H[i][0], v = H[i][1], w = L[i]; ++u; ++v; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } memset(dp, 0x3f, sizeof(dp)); decomposition(1); return ans == inf ? -1 : ans; } // void solve() { // cin >> n >> k; // for(int i = 1, u, v, w; i < n; ++i) { // cin >> u >> v >> w; // ++u; ++v; // g[u].emplace_back(v, w); // g[v].emplace_back(u, w); // } // memset(dp, 0x3f, sizeof(dp)); // decomposition(1); // cout << (ans == inf ? -1 : ans) << '\n'; // } // signed main() { // ios::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // int test = 1; // // cin >> test; // while(test--) solve(); // return 0; // } // https://oj.uz/problem/view/IOI11_race
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...