Submission #1217312

#TimeUsernameProblemLanguageResultExecution timeMemory
1217312NamkhingRace (IOI11_race)C++20
0 / 100
4 ms9024 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<pii> 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, bool option) { if (l > k) return; if (option == 0) ans = min(ans, cnt[k - l] + d); else if (option == 1) cnt[l] = min(cnt[l], d); else cnt[l] = inf; for (auto [v, w] : adj[u]) if (v != p && !used[v]) dfs(v, u, d + 1, l + w, option); } void decom(int u) { u = centroid(u, -1, dfssz(u, -1)); used[u] = true; for (auto [v, w] : adj[u]) { dfs(v, -1, 1, w, 0); dfs(v, -1, 1, w, 1); } for (auto [v, w] : adj[u]) { dfs(v, -1, 1, w, 2); } 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 < MxL; i++) cnt[i] = inf; ans = inf; decom(0); 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...