Submission #971779

#TimeUsernameProblemLanguageResultExecution timeMemory
971779tnknguyen_Race (IOI11_race)C++14
0 / 100
3 ms12124 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define pii pair<int, int> //#define int long long const int MX = 2e5 + 5; vector<pii> gr[MX]; int f[1000005]; int sz[MX], del[MX]; int n, k, ans = 1e9; int dfs(int u, int p){ sz[u] = 1; for(pii e : gr[u]){ int v = e.first; if(v != p && !del[v]){ sz[u] += dfs(v, u); } } return sz[u]; } int centroid(int u, int p, const int &n){ for(pii e : gr[u]){ int v = e.first; if(v != p && !del[v] && sz[v] > n/2){ return centroid(v, u, n); } } return u; } void solve(int u, int p, int dep, int sum, int &ans, const int &op, const int &k){ if(sum > k){ return; } if(op == 1){ ans = min(ans, dep + f[k - sum]); } else{ f[sum] = min(f[sum], dep); } for(pii e : gr[u]){ int v, c; tie(v, c) = e; if(v != p && !del[v]){ solve(v, u, dep + 1, sum + c, ans, op, k); } } } void decompose(int u){ dfs(u, 0); u = centroid(u, 0, sz[u]); del[u] = 1; for(pii e : gr[u]){ int v, c; tie(v, c) = e; if(!del[v]){ solve(v, u, 1, c, ans, 1, k); solve(v, u, 1, c, ans, 2, k); } } for(pii e : gr[u]){ int v, c; tie(v, c) = e; if(!del[v]){ decompose(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], c = L[i]; ++u, ++v; gr[u].push_back({v, c}); gr[v].push_back({u, c}); } fill(f+1, f+K+1, 1e9); decompose(1); return (ans == 1e9 ? -1 : ans); } // int32_t main() { // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); // int n, k; // int h[20][2], l[20]; // cin>>n>>k; // for(int i=0; i<n-1; ++i){ // cin>>h[i][0]>>h[i][1]>>l[i]; // } // cout<<best_path(n, k, h, l); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...