QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #718838 | #5313. Please Save Pigeland | lllei# | RE | 1ms | 3624kb | C++20 | 7.7kb | 2024-11-06 21:35:39 | 2024-11-06 21:35:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL INF = 1e18;
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = init_[l];
return;
}
int mid = (l + r) / 2;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
pull(p);
};
build(1, 0, n - 1);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
template<class F>
void modify(int p, int l, int r, int x, F op) {
if (l == r) {
op(info[p]);
return;
}
int mid = (l + r) >> 1;
push(p);
if (x <= mid) {
modify(2 * p, l, mid, x, op);
} else {
modify(2 * p + 1, mid + 1, r, x, op);
}
pull(p);
}
template<class F>
void modify(int p, const F op) {
modify(1, 0, n - 1, p, op);
}
void modify(int p, int l, int r, int x, const Info &v) {
if (l == r) {
info[p] = v;
return;
}
int mid = (l + r) / 2;
push(p);
if (x <= mid) {
modify(2 * p, l, mid, x, v);
} else {
modify(2 * p + 1, mid + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n - 1, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int mid = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, mid, x, y) + rangeQuery(2 * p + 1, mid + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n - 1, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l > y || r < x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int mid = (l + r) / 2;
push(p);
rangeApply(2 * p, l, mid, x, y, v);
rangeApply(2 * p + 1, mid + 1, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n - 1, l, r, v);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred, Info &pre) {
if (l > y || r < x) {
return -1;
}
if (l >= x && r <= y) {
if (!pred(pre + info[p])) {
pre = pre + info[p];
return -1;
}
}
if (l == r) {
return l;
}
int mid = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, mid, x, y, pred, pre);
if (res == -1) {
res = findFirst(2 * p + 1, mid + 1, r, x, y, pred, pre);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
Info pre;
return findFirst(1, 0, n - 1, l, r, pred, pre);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred, Info &suf) {
if (l > y || r < x) {
return -1;
}
if (l >= x && r <= y) {
if (!pred(info[p] + suf)) {
suf = info[p] + suf;
return -1;
}
}
if (l == r) {
return l;
}
int mid = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, mid + 1, r, x, y, pred, suf);
if (res == -1) {
res = findLast(2 * p, l, mid, x, y, pred, suf);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
Info suf;
return findLast(1, 0, n - 1, l, r, pred, suf);
}
};
struct Tag {
LL add = 0;
void apply(Tag t) & {
add += t.add;
}
};
struct Info {
int len;
LL g, sum;
Info(int len = 0, LL g = 0, LL sum = 0) : len(len), g(g), sum(sum) {}
void apply(Tag t) & {
sum += len * t.add;
}
};
Info operator+(const Info &a, const Info &b) {
return Info(a.len + b.len, gcd(a.g, b.g), a.sum + b.sum);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(k);
vector<bool> vis(n);
vector<int> id(n, -1), rid(n, -1);
int cnt = 0;
for (int i = 0; i < k; ++i) {
cin >> a[i];
--a[i];
vis[a[i]] = true;
}
vector<int> L(n, n), R(n, -1);
vector<vector<array<int, 2>>> e(n);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
vector<LL> dis(n);
auto dfs = [&](auto &&self, int u, int fa) -> void {
if (vis[u]) {
id[u] = cnt;
rid[cnt] = u;
cnt++;
L[u] = R[u] = id[u];
}
for (auto [v, w] : e[u]) {
if (v == fa) {
continue;
}
dis[v] = dis[u] + w;
self(self, v, u);
L[u] = min(L[u], L[v]);
R[u] = max(R[u], R[v]);
}
};
dfs(dfs, 0, -1);
sort(a.begin(), a.end(), [&](int x, int y) {
return id[x] < id[y];
});
vector<Info> init(k);
for (int i = 0; i < k; ++i) {
init[i] = Info(1, i == 0 ? dis[a[i]] : dis[a[i]] - dis[a[i - 1]], dis[a[i]]);
}
LazySegmentTree<Info, Tag> seg(init);
LL ans = INF;
auto myMod = [&](int l, int r, LL w) {
if (l > r) {
return;
}
seg.rangeApply(l, r, {w});
if (r + 1 < k) {
auto op = [&](Info &info) {
info.g -= w;
};
seg.modify(r + 1, op);
}
auto op = [&](Info &info) {
info.g += w;
};
seg.modify(l, op);
};
auto dfs1 = [&](auto &&self, int u, int fa) -> void {
Info info = seg.info[1];
ans = min(ans, info.sum / info.g * 2);
for (auto [v, w] : e[u]) {
if (v == fa) {
continue;
}
if (L[v] <= R[v]) {
myMod(L[v], R[v], -w);
myMod(R[v] + 1, k - 1, w);
myMod(0, L[v] - 1, w);
} else {
myMod(0, k - 1, w);
}
self(self, v, u);
if (L[v] <= R[v]) {
myMod(L[v], R[v], w);
myMod(R[v] + 1, k - 1, -w);
myMod(0, L[v] - 1, -w);
} else {
myMod(0, k - 1, -w);
}
}
};
dfs1(dfs1, 0, -1);
cout << ans << '\n';
return 0;
}
/*
5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: -100
Runtime Error
input:
1 1 1