제출 #648102

#제출 시각아이디문제언어결과실행 시간메모리
648102alvinpiter경주 (Race) (IOI11_race)C++17
21 / 100
3062 ms11780 KiB
/* Subproblem: Given a tree with N nodes, find the minimum number of edges in a path whose total length is exactly K and it either ends at the root or pass through the root. root / | \ .. c_i c_(i + 1) After processing the first i children of the root, let's say we know the following: minEdges[length] -> Minimum number of edges in a path of length "length" such that it originates from the root and ends up at the subtree of the first i children of the root. When processing the (i + 1)-th children, we can utilize that value. For example, we are at a node whose distance from the root is d, then the answer we seek to minize is: depth + minEdges[K - d]. This problem is solved in O(N log N) time. To solve the full problem, we need to perform centroid decomposition. The total complexity will be O(N log^2(N)) */ #include "race.h" #include<bits/stdc++.h> using namespace std; #define INF 1000000000 #define MAXN 200000 int n, k, sz[MAXN + 3]; vector<pair<int, int> > adj[MAXN + 3]; bool isDecomposed[MAXN + 3]; map<int, int> minEdges; int ans = INF; void dfsSize(int u, int prev = -1) { sz[u] = 1; for (auto [v, cost]: adj[u]) { if (v != prev && !isDecomposed[v]) { dfsSize(v, u); sz[u] += sz[v]; } } } int doFindCentroid(int u, int subtreeSize, int prev = -1) { for (auto [v, cost]: adj[u]) { if (v != prev && !isDecomposed[v] && sz[v] * 2 > subtreeSize) { return doFindCentroid(v, subtreeSize, u); } } return u; } int findCentroid(int u) { dfsSize(u); return doFindCentroid(u, sz[u]); } void updateAnswer(int u, int prev, int currentDepth, int currentDist) { if (minEdges.find(k - currentDist) != minEdges.end()) { ans = min(ans, currentDepth + minEdges[k - currentDist]); } for (auto [v, cost]: adj[u]) { if (v != prev) { updateAnswer(v, u, currentDepth + 1, currentDist + cost); } } } void updateMinEdges(int u, int prev, int currentDepth, int currentDist) { if (minEdges.find(currentDist) == minEdges.end()) { minEdges[currentDist] = currentDepth; } else { minEdges[currentDist] = min(minEdges[currentDist], currentDepth); } for (auto [v, cost]: adj[u]) { if (v != prev) { updateMinEdges(v, u, currentDepth + 1, currentDist + cost); } } } void centroidDecomposition(int u) { int centroid = findCentroid(u); isDecomposed[centroid] = true; for (auto [v, cost]: adj[centroid]) { if (!isDecomposed[v]) { updateAnswer(v, centroid, 1, cost); updateMinEdges(v, centroid, 1, cost); } } // Handle paths that end at the centroid if (minEdges.find(k) != minEdges.end()) { ans = min(ans, minEdges[k]); } minEdges.clear(); for (auto [v, cost]: adj[centroid]) { if (!isDecomposed[v]) { centroidDecomposition(v); } } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for (int i = 0; i < n - 1; i++) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } memset(isDecomposed, false, sizeof(isDecomposed)); centroidDecomposition(1); if (ans < INF) { return ans; } else { return -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...