This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #include "race.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int MAXN = 2e5;
const int MAXV = 1e6+1;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];
bool in[MAXN];
int n, k;
void dfs(int v, int pai) {
sz[v] = 1;
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
dfs(viz, v);
sz[v] += sz[viz];
}
}
int find_centroid(int v, int pai, int qty) {
// cout << "buscando centroid " << v << endl;
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
if (sz[viz] > qty / 2) return find_centroid(viz, v, qty);
}
// cout << "é" << v <<endl;
return v;
}
vector<int> sub_mn_depth(MAXV, 1e8);
vector<pair<int, int>> dists[MAXV];
vector<int> sub_dists;
void get_dist(int v, int pai, int dist, int depth) {
if (dist > k) return;
sub_mn_depth[dist] = min(sub_mn_depth[dist], depth);
sub_dists.push_back(dist);
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
get_dist(viz, v, dist + w, depth+1);
}
}
int ans = 1e8;
void decomp(int v) {
dfs(v, -1);
int centroid = find_centroid(v, -1, sz[v]);
in[centroid] = true;
vector<int> all_dists;
// if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
get_dist(viz, centroid, w, 1);
for (int d : sub_dists) {
dists[d].push_back({sub_mn_depth[d], viz});
sort(dists[d].begin(), dists[d].end());
if ((int)dists[d].size() > 2) dists[d].pop_back();
sub_mn_depth[d] = 1e8;
all_dists.push_back(d);
}
sub_dists.clear();
}
if (!dists[k].empty()) ans = min(ans, dists[k][0].first);
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
get_dist(viz, centroid, w, 1);
for (int d : sub_dists) {
for (int i=0; d <= k and i<min(2, (int)dists[k-d].size()); i++) {
if (dists[k-d][i].second == viz) continue;
ans = min(ans, dists[k-d][i].first + sub_mn_depth[d]);
}
sub_mn_depth[d] = 1e8;
}
sub_dists.clear();
}
for (int d : all_dists) dists[d].clear();
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
decomp(viz);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i=0; i<N-1; i++) {
int u = H[i][0], v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(0, -1);
decomp(0);
return (ans == (int)1e8 ? -1 : ans);
}
# | 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... |