Submission #1259374

#TimeUsernameProblemLanguageResultExecution timeMemory
1259374giorgi123glmRace (IOI11_race)C++20
0 / 100
0 ms320 KiB
#include "race.h" #include <functional> #include <iostream> #include <map> #include <vector> using namespace std; int best_path(int N, int K, int H[][2], int L[]) { vector <vector <pair <int, int> > > gr (N); for (int i = 0; i < N - 1; i++) { gr[H[i][0]].emplace_back (H[i][1], L[i]); gr[H[i][1]].emplace_back (H[i][0], L[i]); } vector <bool> dis (N + 1); vector <int> down_sum (N + 1); vector <pair <int, int> > can (K + 1, {0, -1}); int ans = 2e9; int step = 1; auto f = [&](auto& f, int stp)->void { vector <int> points; auto dfs1 = [&](auto& dfs1, int p, int par)->void { down_sum[p] = 1; points.emplace_back (p); for (pair <int, int>& e : gr[p]) if (e.first != par && !dis[e.first]) { dfs1 (dfs1, e.first, p); down_sum[p] += down_sum[e.first]; } }; dfs1 (dfs1, stp, -1); auto dfs2 = [&](auto& dfs2, int p, int par)->int { for (pair <int, int>& e : gr[p]) if (e.first != par && !dis[e.first]) if (down_sum[e.first] > points.size() / 2) return dfs2 (dfs2, e.first, p); return p; }; int centr = dfs2 (dfs2, stp, -1); dis[centr] = 1; can[0] = {0, step}; auto dfs3 = [&](auto& dfs3, int p, int par, int dep, int leng, bool save)->void { if (leng > K) return; if (save) { if (can[leng].second != stp) can[leng] = {dep, step}; else { can[leng].first = min (can[leng].first, dep); } } else { if (can[K - leng].second == stp) ans = min (ans, can[K - leng].first + dep); } for (pair <int, int>& e : gr[p]) if (e.first != par && !dis[e.first]) dfs3 (dfs3, e.first, p, dep + 1, leng + e.second, save); }; for (pair <int, int>& e : gr[centr]) if (!dis[e.first]) { dfs3 (dfs3, e.first, centr, 1, e.second, 0); dfs3 (dfs3, e.first, centr, 1, e.second, 1); } for (pair <int, int>& e : gr[centr]) if (!dis[e.first]) { step++; f (f, e.first); } }; f (f, 0); if (ans == 2e9) return -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...