#include <bits/stdc++.h>
using namespace std;
// #ifdef ONLINE_JUDGE
// #define debug(...)
// #else
// #include "debug.h"
// #endif
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long, long long>
long long ANS = LLONG_MAX;
void dfs_sze(long long u, long long par, vector<vector<pii>> &adj, vector<long long> &sze, vector<long long> &len, vector<long long> &depth) {
sze[u] = 1;
for (auto v : adj[u]) {
if (v.f != par) {
len[v.f] = len[u] + v.s;
depth[v.f] = depth[u] + 1;
dfs_sze(v.f, u, adj, sze, len, depth);
sze[u] += sze[v.f];
}
}
}
void small_to_large_merging(long long K, long long u, long long par, vector<long long> &sze, vector<long long> &len, vector<long long> &depth, vector<vector<pii>> &adj, vector<multiset<pii>> &sets) {
multiset<pii> smalls;
for (auto x : adj[u]) {
if (x.f != par) {
small_to_large_merging(K, x.f, u, sze, len, depth, adj, sets);
if (sz(sets[x.f]) > sz(smalls)) {
swap(sets[x.f], smalls);
}
for (auto y : sets[x.f]) {
long long act_len = y.f - len[u];
long long act_depth = y.s - depth[u];
pii find_pair = {K - act_len + len[u], -1ll};
auto it = smalls.lower_bound(find_pair);
if (it != smalls.end()) {
if (it->f == K + len[u] - act_len) {
ANS = min(ANS, it->s - depth[u] + act_depth);
}
}
}
for (auto y : sets[x.f]) {
smalls.insert(y);
}
}
}
if (sz(smalls) > sz(sets[u])) {
swap(smalls, sets[u]);
}
for (auto x : smalls) {
sets[u].insert(x);
}
sets[u].insert({len[u], depth[u]});
pii find_pair = {K + len[u], -1ll};
auto it = smalls.lower_bound(find_pair);
if (it != smalls.end()) {
if (it->f == K + len[u]) {
ANS = min(ANS, it->s - depth[u]);
}
}
}
int best_path (int N, int k, int H[][2], int L[]) {
ANS = LLONG_MAX;
long long n = N, K = k;
vector<vector<pii>> adj(n);
for (long long i = 0; i < n - 1; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
// debug(adj);
vector<long long> sze(n, 0);
vector<long long> len(n, 0);
vector<long long> depth(n, 0);
dfs_sze(0, -1, adj, sze, len, depth);
// debug(sze, len, depth);
vector<multiset<pii>> sets(n);
small_to_large_merging(K, 0, -1, sze, len, depth, adj, sets);
if (ANS == LLONG_MAX) {
return -1;
}
return ANS;
}
// void solve() {
// int n, K;
// cin >> n >> K;
// int H[n - 1][2];
// int L[n - 1];
// for (long long i = 0; i < n - 1; i++) {
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// long long ans;
// cin >> ans;
// cout << best_path(n, K, H, L) << ' ' << ans << endl;
// }
// signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// long long zz = 1;
// // cin >> zz;
// for (long long i = 1; i <= zz; i++) {
// // cout << "Case #" << i << ": ";
// solve();
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
