제출 #401708

#제출 시각아이디문제언어결과실행 시간메모리
401708sliviu경주 (Race) (IOI11_race)C++14
43 / 100
1156 ms43204 KiB
#include <bits/stdc++.h> using namespace std; int best_path(int n, int k, int h[][2], int l[]) { int ans = INT_MAX; vector<vector<pair<int, int>>> G(n + 1); vector<int> seen(n + 1), s(n + 1); map<int, int> m; for (int i = 0; i < n - 1; ++i) { G[1 + h[i][0]].emplace_back(1 + h[i][1], l[i]); G[1 + h[i][1]].emplace_back(1 + h[i][0], l[i]); } function<void(int, int)> dfs = [&](int node, int last) { s[node] = 1; for (auto x : G[node]) if (x.first != last && !seen[x.first]) { dfs(x.first, node); s[node] += s[x.first]; } }; function<int(int, int, int)> centroid = [&](int node, int last, int n) { for (auto x : G[node]) if (x.first != last && !seen[x.first] && s[x.first] > n / 2) return centroid(x.first, node, n); return node; }; function<void(int, int, int, int)> dfs2 = [&](int node, int last, int length1, int length2) { if (m.count(k - length1)) ans = min(ans, m[k - length1] + length2); for (auto x : G[node]) if (x.first != last && !seen[x.first]) dfs2(x.first, node, length1 + x.second, length2 + 1); if (m.count(length1)) m[length1] = min(m[length1], length2); else m[length1] = length2; }; function<void(int)> Build = [&](int node) { dfs(node, 0); int c = centroid(node, 0, s[node]); seen[c] = 1; m.clear(); m[0] = 0; for (auto x : G[c]) if (!seen[x.first]) dfs2(x.first, c, x.second, 1); for (auto x : G[c]) if (!seen[x.first]) Build(x.first); }; Build(1); return ans != INT_MAX ? ans : -1; };
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...