Submission #1217318

#TimeUsernameProblemLanguageResultExecution timeMemory
1217318NamkhingRace (IOI11_race)C++20
21 / 100
3089 ms12920 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int inf = 1e9; const int MxN = 2e5 + 10; const int MxL = 1e6 + 10; int n, k, ans, sz[MxN], cnt[MxL]; bool used[MxN]; vector<int> res2; vector<pii> res, adj[MxN]; int dfssz(int u, int p) { sz[u] = 1; for (auto [v, w] : adj[u]) if (v != p && !used[v]) sz[u] += dfssz(v, u); return sz[u]; } int centroid(int u, int p, int n) { for (auto [v, w] : adj[u]) if (v != p && !used[v] && sz[v] > n / 2) return centroid(v, u, n); return u; } void dfs(int u, int p, int d, int l) { if (l > k) return; ans = min(ans, d + cnt[k - l]); res.push_back({l, d}); res2.push_back(l); for (auto [v, w] : adj[u]) if (v != p && !used[v]) dfs(v, u, d + 1, l + w); } void decom(int u) { u = centroid(u, -1, dfssz(u, -1)); used[u] = true; for (auto [v, w] : adj[u]) { if (used[v]) continue; dfs(v, u, 1, w); for (auto [l, d] : res) cnt[l] = min(cnt[l], d); res.clear(); } for (auto l : res2) cnt[l] = n; for (auto [v, w] : adj[u]) if (!used[v]) decom(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]; int v = H[i][1]; int w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for (int i = 1; i <= k; i++) cnt[i] = n; ans = n; decom(0); return ans != n ? 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...