| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 854776 | alex_2008 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"#include <iostream>#include <algorithm>#include <map>#include <vector>#include <string>#include <unordered_map>#include <cassert>using namespace std;const int MAX_N = 5e5 + 10;bool used[MAX_N];int subtree[MAX_N], dist[MAX_N], height[MAX_N];int h[MAX_N][2], l[MAX_N];int KK;int ans = MAX_N;vector <vector<pair<int, int>>> G;int find_centroid(int v) { int p = -1; int u = v; while (1) { int x = -1; for (auto it : G[u]) { if (it.first == p) continue; if (used[it.first]) continue; if (2 * subtree[it.first] > subtree[v]) { x = it.first; break; } } if (x == -1) return u; p = u; u = x; }}void dfs(int v, int p) { if (p == -1) { dist[v] = 0; height[v] = 0; } subtree[v] = 1; for (auto it : G[v]) { if (it.first == p || used[it.first]) continue; dist[it.first] = min(dist[v] + it.second, KK + 1); height[it.first] = height[v] + 1; dfs(it.first, v); subtree[v] += subtree[it.first]; }}vector <int> vec;void find_vertexes(int v, int p) { vec.push_back(v); for (auto it : G[v]) { if (used[it.first] || it.first == p) continue; find_vertexes(it.first, v); }}void solve(int v) { dfs(v, -1); v = find_centroid(v); dfs(v, -1); vector <vector<int>> u; for (auto it : G[v]) { if (used[it.first]) continue; vec.clear(); find_vertexes(it.first, v); u.push_back(vec); } unordered_map <int, int> mp; for (auto it : u) { for (auto j : it) { if (mp.find(KK - dist[j]) != mp.end()) { ans = min(ans, height[j] + mp[KK - dist[j]]); } } for (auto j : it) { if (mp.find(dist[j]) == mp.end()) { mp[dist[j]] = height[j]; } else mp[dist[j]] = min(mp[dist[j]], height[j]); } } if (mp.find(KK) != mp.end()) { ans = min(ans, mp[KK]); } used[v] = true; for (auto it : G[v]) { if (used[it.first]) continue; solve(it.first); }}int best_path(int N, int K, int H[][2], int L[]) { KK = K; G.resize(N); for (int i = 0; i < N - 1; i++) { G[H[i][0]].push_back({ H[i][1], L[i] }); G[H[i][1]].push_back({ H[i][0], L[i] }); } solve(0); if (ans == MAX_N) return -1; return ans;}//int main() {// int n, k;// cin >> n >> k;// for (int i = 0; i < n - 1; i++) {// cin >> h[i][0] >> h[i][1];// }// for (int i = 0; i < n - 1; i++) {// cin >> l[i];// }// cout << best_path(n, k, h, l) << "\n";//}