이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
#define NN 200010
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
vector<pl> adj[NN];
struct mp {
ll plen = 0, pwe = 0;
map<ll, ll> mp; // maps weight -> lens, lazy updates and shit
void insert(ll k, ll w) {
if (!mp.count(k-pwe)) mp[k-pwe] = w - plen;
else mp[k-pwe] = min(w - plen, mp[k-pwe]);
}
ll query(ll k) {
if (!mp.count(k-pwe)) return 1e9;
return mp[k-pwe] + plen;
}
vector<pl> getall() const {
vector<pl> res;
for (const auto &[k, v]: mp) res.emplace_back(k + pwe, v + plen);
return res;
}
};
ll ans, k;
mp dfs(ll i, ll p) {
mp cur;
for (auto [x, w]: adj[i]) if (x-p) {
auto child = dfs(x, i);
child.plen++; child.pwe+=w;
if (cur.mp.size() < child.mp.size()) swap(cur, child);
for (const auto [k, v]: child.getall()) {
ans = min(ans, cur.query(k) + v);
cur.insert(k, v);
}
}
ans = min(ans, cur.query(k));
cur.insert(0, 0);
return cur;
}
int best_path(int N, int K, int H[][2], int L[])
{
F(i, 0, N-1) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
ans = N;
k = K;
dfs(0, 0);
return 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... |