제출 #890197

#제출 시각아이디문제언어결과실행 시간메모리
890197anarch_y경주 (Race) (IOI11_race)C++17
0 / 100
4 ms18268 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back const int maxn = 200001; int N, K; vector<int> adj[maxn]; vector<pair<int, int>> adj2[maxn]; int sub[maxn]; bool done[maxn]; int subtree_size(int s, int p){ sub[s] = 1; for(auto u: adj[s]){ if(u == p or done[u]) continue; sub[s] += subtree_size(u, s); } return sub[s]; } int get_centroid(int s, int p, int num){ for(auto u: adj[s]){ if(u == p or done[u]) continue; if(2*sub[u] > num) return get_centroid(u, s, num); } return s; } int min_d[1000001] = {0}; int mxd; int ans = 1e9; void calc(int s, int p, int ok, int d, int wt){ if(wt > K) return; mxd = max(mxd, wt); if(ok) min_d[wt] = min(min_d[wt], d); else ans = min(ans, d+min_d[K-wt]); for(auto &[u, t]: adj2[s]){ if(u == p or done[u]) continue; calc(u, s, ok, d+1, wt+t); } } void centroid_decomp(int s){ int num = subtree_size(s, 0); int cent = get_centroid(s, 0, num); int mxd = 0; for(auto &[u, w]: adj2[cent]){ if(done[u]) continue; calc(u, cent, false, 1, w); calc(u, cent, true, 1, w); } fill(min_d+1, min_d+mxd+1, 1e9); done[cent] = true; for(auto u: adj[cent]){ if(!done[u]) centroid_decomp(u); } } 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 a = H[i][0], b = H[i][1], w = L[i]; adj[a].pb(b); adj[b].pb(a); adj2[a].pb({b, w}); adj2[b].pb({a, w}); } fill(min_d+1, min_d+1000001, 1e9); centroid_decomp(1); return (ans != 1e9 ? 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...