Submission #1154229

#TimeUsernameProblemLanguageResultExecution timeMemory
1154229hiderrRace (IOI11_race)C++20
21 / 100
3094 ms12012 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define loop(i, a, b) for(int i = a; i <= b; i++) #define loop_rev(i, a, b) for(int i = a; i >= b; i--) #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define eb emplace_back #define pb push_back using ll = int64_t; vector<vector<pair<int, int>>> graph; vector<int> sub, blocked; int n, k; void prep_sub(int v, int p) { sub[v] = 1; for(auto [ s, _ ] : graph[v]) { if(s == p || blocked[s]) continue; prep_sub(s, v); sub[v] += sub[s]; } } int find_centroid(int v, int p) { for(auto [ s, _ ] : graph[v]) { if(s == p || blocked[s]) continue; if(sub[s] > n/2) { return find_centroid(s, v); } } return v; } constexpr int inf = 1e9; vector<pair<int, int>> new_distances; vector<int> all_distances; vector<int> minim; void prep_dist(int v, int p, pair<int, int> dist) { if(dist.first > k || blocked[v]) return; new_distances.pb(dist); for(auto [ s, w ] : graph[v]) { if(s == p) continue; prep_dist(s, v, { dist.first + w, dist.second + 1 }); } } int res = inf; void solve(int rep) { if(blocked[rep]) return; prep_sub(rep, (-1)); int centroid = find_centroid(rep, (-1)); all_distances = { 0 }, minim[0] = 0; for(auto [ s, w ] : graph[centroid]) { prep_dist(s, centroid, { w, 1 }); for(auto [ d, len ] : new_distances) { res = min(res, minim[k - d] + len); } for(auto [ d, len ] : new_distances) { minim[d] = min(minim[d], len); all_distances.pb(d); } new_distances.clear(); } for(int d : all_distances) { minim[d] = inf; } blocked[centroid] = 1; for(auto [ s, _ ] : graph[centroid]) { solve(s); } } int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; graph.resize(n); loop(i, 0, n-2) { graph[H[i][0]].pb({ H[i][1], L[i] }); graph[H[i][1]].pb({ H[i][0], L[i] }); } minim.resize(k + 1, inf); blocked.resize(n); sub.resize(n); solve(0); if(res == inf) { return (-1); } else { return res; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...