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 <bits/stdc++.h>
#include <race.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 2e5 + 3;
int n, k;
long long h[N];
vector<pair<int, int>> adj[N];
int sz[N], heavy[N], dep[N];
void pre_dfs(int u, int p) {
sz[u] = 1; heavy[u] = -1;
for (pair<int, int> &x: adj[u]) if (x.fi != p) {
int v = x.fi, w = x.se;
dep[v] = dep[u] + 1;
h[v] = h[u] + w;
pre_dfs(v, u);
sz[u] += sz[v];
if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
int LCA, ans = N;
vector<pair<long long, int>> store;
map<pair<long long, int>, int> cnt;
void update(int u, int p, int delta) {
if (delta == +1) {
pair<long long, int> need(k + 2 * h[LCA] - h[u], -1);
store.push_back({h[u], dep[u]});
auto it = cnt.lower_bound(need);
if (it != cnt.end() && (*it).fi.fi == need.fi)
mini(ans, dep[u] + (*it).fi.se - 2 * dep[LCA]);
} else {
cnt[{h[u], dep[u]}]--;
if (!cnt[{h[u], dep[u]}]) cnt.erase({h[u], dep[u]});
}
for (pair<int, int> &x: adj[u]) if (x.fi != p) update(x.fi, u, delta);
}
void dfs(int u, int p) {
for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) {
dfs(x.fi, u); update(x.fi, u, -1);
}
if (heavy[u] != -1) {
dfs(heavy[u], u); LCA = u;
for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) {
update(x.fi, u, +1);
while (store.size()) {
cnt[store.back()]++;
store.pop_back();
}
}
}
auto it = cnt.lower_bound({h[u] + k, -1});
if (it != cnt.end() && (*it).fi.fi == h[u] + k)
mini(ans, (*it).fi.se - dep[u]);
cnt[{h[u], dep[u]}]++;
}
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], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
pre_dfs(0, -1); dfs(0, -1);
return (ans == N ? -1 : ans);
}
/*
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> k;
for (int i = 1; i < n; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
pre_dfs(0, -1); dfs(0, -1);
cout << (ans == N ? -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... |