이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = 2e5 + 5;
vector<pair<int, int>> adj[NMAX];
int sz[NMAX];
bool removed[NMAX];
int get_size(int u, int e) {
sz[u] = 1;
for (auto&x : adj[u]) {
int v = x.first;
if (v == e || removed[v]) continue;
sz[u] += get_size(v, u);
}
return sz[u];
}
int get_centroid(int u, int e, int s) {
for (auto&x : adj[u]) {
int v = x.first;
if (v == e || removed[v] || sz[v] <= s/2) continue;
return get_centroid(v, u, s);
}
return u;
}
int dist[NMAX], depth[NMAX], ans = 1e18;
void dfs(int u, int e, int K, map<int, int>&edge) {
if (edge.count(K - dist[u])) ans = min(ans, depth[u] + edge[K - dist[u]]);
for (auto&x : adj[u]) {
int v = x.first, c = x.second;
if (v == e || removed[v]) continue;
dist[v] = dist[u] + c, depth[v] = depth[u] + 1;
dfs(v, u, K, edge);
}
if (!edge.count(dist[u])) edge[dist[u]] = depth[u];
edge[dist[u]] = min(edge[dist[u]], depth[u]);
}
void build(int u, int e, int K) {
int s = get_size(u, e), centroid = get_centroid(u, e, s);
map<int, int> edge;
edge[0] = 0, dist[centroid] = depth[centroid] = 0;
dfs(centroid, -1, K, edge);
removed[centroid] = true;
for (auto&x : adj[centroid]) {
int v = x.first;
if (v == e || removed[v]) continue;
build(v, centroid, K);
}
}
signed best_path(signed N, signed K, signed H[][2], signed L[]) {
for (int i = 0; i < N - 1; i++) {
int u = H[i][0], v = H[i][1], c = L[i];
adj[u].push_back({v, c}), adj[v].push_back({u, c});
}
build(0, -1, K);
return ans == 1e18 ? -1 : ans;
}
/*signed N, K, H[NMAX][2], L[NMAX];
signed main() {
cin >> N >> K;
for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
cout << best_path(N, K, H, L) << '\n';
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |