Submission #1262612

#TimeUsernameProblemLanguageResultExecution timeMemory
1262612denilbRace (IOI11_race)C++20
0 / 100
4 ms9024 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1e9; const int maxn = 200005; const int maxk = 1000005; int sz[maxn], rem[maxn], length[maxk]; vector<pair<int,int>> adj[maxn]; int n, k, ans; int get_sz(int v, int p=-1){ sz[v] = 1; for(auto [u, w]: adj[v]){ if(u == p || rem[u]) continue; sz[v] += get_sz(u, v); } return sz[v]; } int get_centroid(int tsz, int v, int p=-1){ for(auto [u, w]: adj[v]){ if(u == p || rem[u]) continue; if(2 * sz[u] > tsz) return get_centroid(tsz, u, v); } return v; } void dfs(int v, int p, int w, int d, int filling){ if(w > k) return; if(filling == 1) length[w] = min(length[w], d); if(filling == -1) length[w] = inf; if(filling == 0) ans = min(ans, length[k-w] + d); for(auto [u, nw]: adj[v]){ if(u == p || rem[u]) continue; dfs(u, v, w+nw, d+1, filling); } } void centroid_decomp(int v){ int centroid = get_centroid(get_sz(v), v); rem[centroid] = true; for(auto [u, w]: adj[centroid]){ if(rem[u]) continue; dfs(u, centroid, w, 1, 0); dfs(u, centroid, w, 1, 1); } for(auto [u, w]: adj[centroid]){ if(rem[u]) continue; dfs(u, centroid, w, 1, -1); 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 u=H[i][0], v=H[i][1]; adj[u].push_back(make_pair(v, L[i])); adj[v].push_back(make_pair(u, L[i])); } fill(length+1, length+maxk, inf); length[0] = 0; ans = inf; centroid_decomp(0); if(ans == inf) ans = -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...