Submission #1177846

#TimeUsernameProblemLanguageResultExecution timeMemory
1177846MinhKienRace (IOI11_race)C++20
100 / 100
281 ms28976 KiB
#include <iostream> #include <vector> using namespace std; #define ii pair <int, int> #define fi first #define se second const int N = 2e5 + 10; const int M = 1e6 + 10; int n, k, x, y, w; vector <ii> v[N]; int sz[N], dis[M]; bool solved[N]; int calc_size(int s, int p = -1) { sz[s] = 1; for (ii z: v[s]) { if (z.fi == p || solved[z.fi]) continue; sz[s] += calc_size(z.fi, s); } return sz[s]; } int FindCentroid(int s, int Size, int p = -1) { for (ii z: v[s]) { if (z.fi == p || solved[z.fi]) continue; if (sz[z.fi] > Size) return FindCentroid(z.fi, Size, s); } return s; } int ans = 1e9, mx; void run(int s, int p, int depth, int len, bool filling) { if (len > k) return; mx = max(mx, len); if (filling) { if (dis[len] == 0) dis[len] = depth; else dis[len] = min(dis[len], depth); } else { if (dis[k - len] != 0) ans = min(ans, dis[k - len] + depth); if (len == k) ans = min(ans, depth); } for (ii z: v[s]) { if (z.fi == p || solved[z.fi]) continue; run(z.fi, s, depth + 1, len + z.se, filling); } } void CentroidDecomp(int s = 1) { int cen = FindCentroid(s, calc_size(s) >> 1); solved[cen] = true; mx = 0; for (ii z: v[cen]) { if (solved[z.fi]) continue; run(z.fi, cen, 1, z.se, false); run(z.fi, cen, 1, z.se, true); } fill_n(dis, mx + 1, 0); for (ii z: v[cen]) { if (solved[z.fi]) continue; CentroidDecomp(z.fi); } } int best_path(int NN, int KK, int H[][2], int L[]) { n = NN; k = KK; for (int i = 0; i < n - 1; ++i) { x = H[i][0], y = H[i][1], w = L[i]; ++x, ++y; v[x].push_back(ii(y, w)); v[y].push_back(ii(x, w)); } CentroidDecomp(); if (ans == 1e9) 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...