제출 #998148

#제출 시각아이디문제언어결과실행 시간메모리
998148alexdumitru경주 (Race) (IOI11_race)C++14
21 / 100
112 ms27476 KiB
#include "race.h" #include <iostream> #include <vector> using namespace std; const int NMAX = 1e5; const int KMAX = 1e6; vector<pair<int, int>> g[NMAX]; int w[NMAX]; bool used[NMAX]; int minDepth[KMAX + 1]; int Ans; int get_w(int node, int dad) { w[node] = 1; for (auto it : g[node]) { if (it.first == dad || used[it.first]) continue; get_w(it.first, node); w[node] += w[it.first]; } return w[node]; } int get_centroid(int node, int dad, int totalW) { for (auto it : g[node]) { if (it.first == dad || used[it.first]) continue; if (w[it.first] > totalW / 2) return get_centroid(it.first, node, totalW); } return node; } void dfs_add(int node, int dad, int k, int length, int depth) { if (length > k) return; minDepth[length] = min(minDepth[length], depth); for (auto it : g[node]) { if (it.first == dad || used[it.first]) continue; dfs_add(it.first, node, k, length + it.second, depth + 1); } } void dfs_compute(int node, int dad, int k, int length, int depth) { if (length > k) return; Ans = min(Ans, depth + minDepth[k - length]); for (auto it : g[node]) { if (it.first == dad || used[it.first]) continue; dfs_compute(it.first, node, k, length + it.second, depth + 1); } } void dfs_clear(int node, int dad, int k, int length) { if (length > k) return; minDepth[length] = NMAX; for (auto it : g[node]) { if (it.first == dad || used[it.first]) continue; dfs_clear(it.first, node, k, length + it.second); } } void go(int node, int k) { int totalW = get_w(node, -1); int c = get_centroid(node, -1, totalW); used[c] = true; minDepth[0] = 0; for (auto it : g[c]) { if (used[it.first]) continue; dfs_compute(it.first, -1, k, it.second, 1); dfs_add(it.first, -1, k, it.second, 1); } dfs_clear(c, -1, k, 0); for (auto it : g[c]) if (!used[it.first]) go(it.first, k); } int best_path(int N, int K, int H[][2], int L[]) { Ans = N; for (int i = 0; i <= KMAX; i++) { minDepth[i] = N + 1; } for (int i = 0; i < N - 1; i++) { g[H[i][0]].emplace_back(H[i][1], L[i]); g[H[i][1]].emplace_back(H[i][0], L[i]); } go(0, K); return Ans == N ? -1 : 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...