QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252733 | #5313. Please Save Pigeland | ricofx | WA | 564ms | 76516kb | C++20 | 3.4kb | 2023-11-16 09:14:35 | 2023-11-16 09:14:36 |
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;
#define int long long
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 + 1 <= k) modify(1, 1, k, r + 1, -v);
if (r + 2 <= k) modify(1, 1, k, r + 2, v);
}
ll ans, sum;
void dfs1(int u, int fa) {
ans = min(ans, sum / get(1, k));
//cout << u << ' ' << sum << ' ' << get() << ' ' << get(1, k) << '\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';
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(1, k, 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(1, k, -w);
modify(1, k, -w);
}
}
}
void solve() {
cin >> n >> k;
if (k == 1) {
cout << "0\n";
return;
}
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';
}
signed 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: 32328kb
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: 0ms
memory: 34344kb
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: 0
Accepted
time: 3ms
memory: 17904kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 15924kb
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 32336kb
input:
100 10 3 27 33 45 48 72 76 91 92 100 66 98 4 70 17 2 28 59 4 26 25 3 77 92 1 40 61 2 11 27 2 85 35 1 57 26 1 68 99 4 50 84 1 20 82 3 31 39 1 71 7 4 54 55 4 60 26 4 56 61 2 15 66 3 95 53 2 8 60 4 21 82 1 18 81 2 29 73 3 94 4 1 10 4 4 86 43 1 62 41 1 45 57 1 25 66 3 69 89 2 14 53 3 27 92 1 42 98 4 13 ...
output:
200
result:
ok 1 number(s): "200"
Test #6:
score: 0
Accepted
time: 0ms
memory: 34368kb
input:
100 90 75 17 78 84 52 69 54 24 74 35 58 51 72 7 21 70 93 15 60 87 13 40 23 92 99 53 27 22 91 46 56 86 61 19 44 98 50 28 14 12 55 64 30 80 95 38 18 43 31 89 20 16 8 65 63 79 59 34 97 25 2 11 67 71 29 9 37 76 77 26 39 68 32 62 90 10 85 49 42 45 96 83 94 3 6 100 81 57 88 47 67 65 1 43 78 4 98 71 3 71 2...
output:
1798
result:
ok 1 number(s): "1798"
Test #7:
score: 0
Accepted
time: 3ms
memory: 34516kb
input:
1000 10 111 240 479 530 572 583 644 652 753 869 121 923 2 886 685 4 446 284 4 352 250 1 540 485 2 72 154 4 522 693 3 664 917 4 792 941 3 132 832 4 709 186 3 509 114 2 824 978 2 216 265 2 138 570 1 498 959 4 434 222 1 803 693 1 253 677 4 172 463 3 383 978 2 718 959 3 369 421 4 568 454 4 256 938 1 6 1...
output:
226
result:
ok 1 number(s): "226"
Test #8:
score: 0
Accepted
time: 4ms
memory: 36472kb
input:
1000 957 233 514 228 739 827 85 840 175 766 807 19 276 549 611 145 511 895 121 116 525 280 431 810 629 990 509 542 324 241 801 849 506 178 176 49 528 221 742 444 513 111 505 442 794 107 392 291 674 298 803 198 927 738 590 706 804 860 512 421 618 697 516 335 420 418 288 544 694 330 776 104 510 621 47...
output:
32602
result:
ok 1 number(s): "32602"
Test #9:
score: -100
Wrong Answer
time: 564ms
memory: 76516kb
input:
500000 4 182462 188845 259396 281751 456733 79213 9204078 395954 45205 3919968 454058 310013 734433 433648 435834 3887333 448797 138275 9946222 385528 63721 3037094 44276 184047 1799127 169565 81666 3752583 459111 229807 5534913 374868 374333 8627923 476055 408523 2692999 445258 424229 3038119 92885...
output:
184062504
result:
wrong answer 1st numbers differ - expected: '193870600', found: '184062504'