제출 #166020

#제출 시각아이디문제언어결과실행 시간메모리
166020JustInCase경주 (Race) (IOI11_race)C++17
31 / 100
353 ms30812 KiB
#include <iostream> #include <vector> #include <cstring> const int32_t MAX_N = 2e5; #ifdef LOCAL #include "grader.cpp" #endif #ifndef LOCAL #include "race.h" #endif struct Vertex { bool solved; int32_t subtree; std::vector< std::pair< int32_t, int32_t > > v; }; int32_t k, ans = -1, dists[MAX_N + 5]; Vertex g[MAX_N + 5]; void dfs_subtree(int32_t u, int32_t par) { g[u].subtree = 1; for(auto &e : g[u].v) { auto v = e.first; if(!g[v].solved && v != par) { dfs_subtree(v, u); g[u].subtree += g[v].subtree; } } } int32_t dfs_centroid(int32_t u, int32_t par, int32_t subtree) { for(auto &e : g[u].v) { auto v = e.first; if(!g[v].solved && v != par && g[v].subtree > subtree / 2) { return dfs_centroid(v, u, subtree); } } return u; } void dfs_ans(int32_t u, int32_t par, int32_t d, int32_t cntEdges) { if(d > k) { return; } if(dists[k - d] != -1) { if(ans == -1 || ans > cntEdges + dists[k - d]) { ans = cntEdges + dists[k - d]; } } for(auto &e : g[u].v) { auto v = e.first; auto w = e.second; if(!g[v].solved && v != par) { dfs_ans(v, u, d + w, cntEdges + 1); } } } void dfs_add(int32_t u, int32_t par, int32_t d, int32_t cntEdges) { if(d > k) { return; } if(dists[d] == -1 || dists[d] > cntEdges) { dists[d] = cntEdges; } for(auto &e : g[u].v) { auto v = e.first; auto w = e.second; if(!g[v].solved && v != par) { dfs_add(v, u, d + w, cntEdges + 1); } } } void dfs_clear(int32_t u, int32_t par, int32_t d) { if(d > k) { return; } dists[d] = -1; for(auto &e : g[u].v) { auto v = e.first; auto w = e.second; if(!g[v].solved && v != par) { dfs_clear(v, u, d + w); } } } void solve(int32_t u) { dfs_subtree(u, -1); int32_t centroid = dfs_centroid(u, -1, g[u].subtree); dists[0] = 0; for(auto &e : g[centroid].v) { auto v = e.first; if(!g[v].solved) { dfs_ans(v, centroid, e.second, 1); dfs_add(v, centroid, e.second, 1); } } dfs_clear(centroid, -1, 0); g[centroid].solved = true; for(auto &e : g[centroid].v) { auto v = e.first; if(!g[v].solved) { solve(v); } } } int32_t best_path(int32_t n, int32_t _k, int32_t h[][2], int32_t l[]) { k = _k; for(int32_t i = 0; i < n - 1; i++) { g[h[i][0]].v.push_back({ h[i][1], l[i] }); g[h[i][1]].v.push_back({ h[i][0], l[i] }); } memset(dists, -1, sizeof(dists)); solve(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...