Submission #826114

#TimeUsernameProblemLanguageResultExecution timeMemory
826114SoulKnightRace (IOI11_race)C++17
100 / 100
2422 ms53964 KiB
#include "race.h" #include "bits/stdc++.h" using namespace std; #define ll long long #define ln '\n' const int N = 2e5 + 5; const int LG = 20; const int INF = 0x3f3f3f3f; const int MOD = 998244353; int n, k; int h[N][2], l[N]; int sz[N], ans = INF; vector<pair<int, int>> adj[N]; bitset<N> removed; map<ll, int> mn; void init(){ cin >> n >> k; for (int i = 0; i < n-1; i++) cin >> h[i][0] >> h[i][1] >> l[i]; } int get_size(int u, int p){ sz[u] = 1; for (auto& [v, e]: adj[u]){ if (v == p || removed[v]) continue; sz[u] += get_size(v, u); } return sz[u]; } int get_centroid(int u, int p, int s){ for (auto& [v, e]: adj[u]){ if (v == p || removed[v]) continue; if (sz[v] > s / 2) return get_centroid(v, u, s); } return u; } void dfs(int u, int p, int dep, int cur_len, int m){ // cout << u << ' ' << p << ' ' << dep << ' ' << cur_len << ' ' << m << ln; if (cur_len > k) return; if (mn.find(k-cur_len) == mn.end()) mn[k-cur_len] = INF; if (mn.find(cur_len) == mn.end()) mn[cur_len] = INF; if (m == 1) {ans = min(ans, dep + mn[k-cur_len]);} else mn[cur_len] = min(mn[cur_len], dep); for (auto& [v, e]: adj[u]){ if (v == p || removed[v]) continue; dfs(v, u, dep+1, cur_len + e, m); } } void build(int u){ int c = get_centroid(u, -1, get_size(u, -1)); // cout << "centroid " << c << ln; removed[c] = 1; for (auto& [v, e]: adj[c]){ if (removed[v]) continue; dfs(v, c, 1, e, 1); dfs(v, c, 1, e, 0); } // cout << ans << ln; mn.clear(); mn[0] = 0; for (auto& [v, e]: adj[c]){ if (removed[v]) continue; build(v); } } int solve(){ for (int i = 0; i < n-1; i++){ adj[h[i][0]].push_back({h[i][1], l[i]}); adj[h[i][1]].push_back({h[i][0], l[i]}); } mn[0] = 0; build(1); return ((ans == INF)? -1: ans); } void init(int N, int K, int H[][2], int L[]){ n = N; k = K; for (int i = 0; i < n-1; i++){ h[i][0] = H[i][0]; h[i][1] = H[i][1]; l[i] = L[i]; } } int best_path(int N, int K, int H[][2], int L[]) { init(N, K, H, L); return solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...