QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252722 | #5313. Please Save Pigeland | ricofx | RE | 3ms | 34436kb | C++20 | 3.4kb | 2023-11-16 08:49:13 | 2023-11-16 08:49:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int dfc;
int n, k, c[N], rc[N], dfn[N], rnk[N], fr[N], gr[N], dep[N], b[N], id[N], siz[N];
vector<pair<int, int>> G[N];
void dfs(int u, int fa) {
dfn[u] = ++dfc;
rnk[dfc] = u;
siz[u] = 1;
for (auto [v, w] : G[u]) if (v != fa) {
dep[v] = dep[u] + w;
dfs(v, u);
siz[u] += siz[v];
}
}
int tr[N];
void add(int x, int v) {
for (; x <= k; x += x & -x) tr[x] += v;
}
int qry(int x) {
int res = 0;
for (; x; x -= x & -x) res += tr[x];
return res;
}
void add(int l, int r, int v) {
add(l, v), add(r + 1, -v);
}
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
int gc[N];
void build(int p, int l, int r) {
if (l == r) {
gc[p] = b[l];
return;
}
build(lson, l, mid), build(rson, mid + 1, r);
gc[p] = gcd(gc[lson], gc[rson]);
}
void modify(int p, int l, int r, int pos, int det) {
if (l == r) {
gc[p] += det;
return;
}
if (pos <= mid) modify(lson, l, mid, pos, det);
else modify(rson, mid + 1, r, pos, det);
gc[p] = gcd(gc[lson], gc[rson]);
}
int query(int p, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (l >= L && r <= R) return gc[p];
return gcd(query(lson, l, mid, L, R), query(rson, mid + 1, r, L, R));
}
int get(int l = 1, int r = k) {
return gcd(qry(l), l == r ? 0 : query(1, 1, k, l + 1, r));
}
void modify(int l, int r, int v) {
if (l > r) return;
modify(1, 1, k, l, v);
if (l != k) modify(1, 1, k, l + 1, -v);
if (r != k) modify(1, 1, k, r, -v);
if (r + 1 <= k) modify(1, 1, k, r + 1, v);
}
ll ans, sum;
void dfs1(int u, int fa) {
ans = min(ans, sum / get(1, k));
//cout << u << ' ' << sum << ' ' << get() << '\n';
for (auto [v, w] : G[u]) if (v != fa) {
int l = gr[dfn[v]], r = fr[dfn[v] + siz[v] - 1];
// cout << "* " << v << ' '<< l << ' ' << r << '\n';
l = max(l, 1);
if (l <= r) {
add(l, r, -w);
if (l != 1) add(1, l - 1, w);
if (r != k) add(r + 1, k, w);
modify(l, r, -w);
modify(1, l - 1, w);
modify(r + 1, k, w);
sum += (k - 2ll * (r - l + 1)) * w;
} else {
sum += k * w;
add(l, r, w);
modify(1, k, w);
}
dfs1(v, u);
if (l <= r) {
add(l, r, w);
if (l != 1) add(1, l - 1, -w);
if (r != k) add(r + 1, k, -w);
modify(l, r, w);
modify(1, l - 1, -w);
modify(r + 1, k, -w);
sum -= (k - 2ll * (r - l + 1)) * w;
} else {
sum -= k * w;
add(l, r, -w);
modify(1, k, -w);
}
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> c[i];
rc[c[i]] = 1;
}
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
dfs(1, 1);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (rc[rnk[i]]) fr[i] = ++cnt, id[cnt] = rnk[i];
else fr[i] = fr[i - 1];
}
cnt = k + 1;
gr[n + 1] = inf;
for (int i = n; i; i--) {
if (rc[rnk[i]]) gr[i] = --cnt;
else gr[i] = gr[i + 1];
}
cnt = 0;
for (int i = 1; i <= k; i++) b[i] = dep[id[i]] - dep[id[i - 1]];
for (int i = 1; i <= k; i++) add(i, b[i]), sum += dep[id[i]];
build(1, 1, k);
ans = 1e18;
dfs1(1, 1);
cout << ans * 2 << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
//cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32324kb
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: 3ms
memory: 34436kb
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