QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118774 | #6629. Travelling Trader | Qwerty1232# | 2 | 127ms | 34660kb | C++23 | 6.0kb | 2023-07-04 02:42:25 | 2024-05-31 18:56:40 |
Judging History
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<std::vector<int>> gr(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
gr[u].push_back(v);
gr[v].push_back(u);
}
std::vector<int> p(n);
for (int& i : p) {
std::cin >> i;
}
p.push_back(0);
{
auto dfs = [&](auto dfs, int v, int f) -> void {
auto it = std::find(gr[v].begin(), gr[v].end(), f);
if (it != gr[v].end()) {
gr[v].erase(it);
}
for (int& t : gr[v]) {
dfs(dfs, t, v);
}
};
dfs(dfs, 0, -1);
}
if (k == 1) {
std::vector<int64_t> dist(n, 0);
std::vector<int> prv(n, -1);
auto dfs = [&](auto dfs, int v, int f, int64_t d) -> void {
prv[v] = f;
dist[v] = d;
for (int t : gr[v]) {
dfs(dfs, t, v, d + p[t]);
}
};
dfs(dfs, 0, -1, p[0]);
int it = std::max_element(dist.begin(), dist.end()) - dist.begin();
int v = it;
std::vector<int> ans;
while (v != -1) {
ans.push_back(v);
v = prv[v];
}
std::reverse(ans.begin(), ans.end());
std::cout << dist[it] << "\n";
std::cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
std::cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}
return 0;
}
if (k == 3) {
return 0;
std::vector<int> tin(n), tout(n), depth(n);
int e = 0;
auto dfs = [&](auto dfs, int v, int d) -> void {
tin[v] = e++;
depth[v] = d;
for (int t : gr[v]) {
dfs(dfs, t, d + 1);
}
tout[v] = e++;
};
dfs(dfs, 0, 0);
int64_t ans_val = std::accumulate(p.begin(), p.end(), 0ll);
std::vector<int> ans(n);
std::iota(ans.begin(), ans.end(), 0);
std::sort(ans.begin(), ans.end(), [&](int a, int b) {
auto get = [&](int i) {
if (depth[i] % 2) {
return tout[i];
}
return tin[i];
};
return get(a) < get(b);
});
std::cout << ans_val << "\n";
std::cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
std::cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}
return 0;
}
if (k == 2) {
std::vector<std::pair<int64_t, int>> dp(n + 1);
std::vector<std::pair<int64_t, std::pair<int, int>>> dp2(n + 1);
auto dfs = [&](auto dfs, int v) -> void {
int64_t sum = 0;
for (int t : gr[v]) {
sum += p[t];
dfs(dfs, t);
}
if (gr[v].empty()) {
dp[v] = {p[v], n};
dp2[v] = {p[v], {n, n}};
return;
}
for (int t : gr[v]) {
dp[v] = std::max(dp[v], {p[v] + sum - p[t] + dp[t].first, t});
}
std::array<int, 3> cum1, cum2;
cum1.fill(n);
cum2.fill(n);
for (int t : gr[v]) {
cum1[2] = t;
std::sort(cum1.begin(), cum1.end(), [&](int a, int b) { return dp[a] > dp[b]; });
cum2[2] = t;
std::sort(cum2.begin(), cum2.end(), [&](int a, int b) { return dp2[a] > dp2[b]; });
}
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
if (cum1[a] != cum2[b]) {
dp2[v] = std::max(dp2[v], {p[v] + sum - p[cum1[a]] - p[cum2[b]] + dp[cum1[a]].first + dp2[cum2[b]].first, {cum1[a], cum2[b]}});
}
}
}
};
dfs(dfs, 0);
auto get_cum = [&](int v) {
std::deque<int> res;
bool rev = false;
auto add = [&](bool back, int val) {
assert(res.size() < 1e6);
if (back != rev) {
res.push_back(val);
} else {
res.push_front(val);
}
};
auto f = [&](auto f, int v) -> void {
if (v == n) {
return;
}
int nxt = dp[v].second;
for (int t : gr[v]) {
if (t != nxt) {
add(0, t);
}
}
f(f, nxt);
rev = !rev;
add(0, v);
};
f(f, v);
if (rev) {
std::reverse(res.begin(), res.end());
}
return std::vector<int>(res.begin(), res.end());
};
int v = 0;
std::vector<int> ans;
while (v != n) {
auto [val, pp] = dp2[v];
auto [a, b] = pp;
ans.push_back(v);
auto vc = get_cum(a);
ans.insert(ans.end(), vc.begin(), vc.end());
for (int t : gr[v]) {
if (t != a && t != b) {
ans.push_back(t);
}
}
v = b;
assert(ans.size() < 1e6);
}
std::vector<bool> used(n);
for (int i : ans) {
used[i] = true;
}
int64_t val_ans = 0;
for (int i = 0; i < n; i++) {
val_ans += used[i] * p[i];
}
assert(val_ans == dp2[0].first);
std::cout << dp2[0].first << "\n";
std::cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
std::cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 0ms
memory: 3620kb
input:
2 1 1 2 255959470 961356354
output:
1217315824 2 1 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
1000 1 730 89 762 280 923 523 740 22 679 350 448 769 102 712 154 965 219 32 238 289 484 502 183 311 999 682 806 450 275 101 131 197 749 720 131 937 960 202 503 320 95 262 595 133 809 560 659 451 843 218 258 842 564 316 729 727 413 237 606 531 469 258 612 8 707 539 359 680 957 639 381 708 104 490 234...
output:
95535 17 1 173 449 472 396 545 668 270 981 489 852 836 763 6 218 843 758
result:
ok correct!
Test #3:
score: 0
Accepted
time: 66ms
memory: 17276kb
input:
200000 1 111811 133538 179217 151840 171974 117009 187613 169656 64662 13136 132434 89348 52802 175565 194821 191312 196047 99457 40339 152969 29669 180026 147677 57771 119598 58048 80707 146623 72232 101624 48109 11800 71536 69 31573 129 24409 17263 1033 148614 66977 149926 138624 87653 141889 1178...
output:
221 35 1 145832 90178 52464 3517 55709 39776 67451 59386 143855 102872 38865 13093 177086 7366 190908 160039 69864 196809 13257 612 171083 182883 14221 93359 52156 27994 103745 151704 138607 5346 14735 29598 89600 128747
result:
ok correct!
Test #4:
score: 0
Accepted
time: 76ms
memory: 17348kb
input:
200000 1 102636 78442 179388 84484 161437 35179 102313 154299 62439 71542 176361 125315 174129 186376 180886 54947 154823 114239 174647 112385 136495 187134 157035 96260 101101 192444 58209 23947 55494 191600 168007 162648 140149 73180 130665 180633 129328 67380 90262 134914 185905 104220 111321 154...
output:
21795891322 36 1 13557 199188 104317 71891 69787 1221 63258 191536 179446 83510 187880 124824 43888 83237 194602 59080 196038 195977 18490 43421 110298 60011 137785 140692 48345 68279 128780 198550 29394 56331 112092 192199 177180 16418 142142
result:
ok correct!
Test #5:
score: 0
Accepted
time: 65ms
memory: 17212kb
input:
200000 1 682 75953 92444 160568 113369 93705 154622 193304 149619 128186 104784 48913 131684 161196 25886 151867 89191 19511 99233 137377 104650 120096 64347 93526 111350 71598 7568 120116 123497 76821 25436 190715 99884 33654 109438 69462 165464 2475 163215 34551 33926 85078 101208 193355 50705 828...
output:
99327575017 197 1 178606 82034 53029 10508 21404 203 109187 121716 142023 3901 36728 9916 192913 18250 170199 113960 179753 163922 179588 31797 31645 183321 83207 13973 128176 38001 160968 9055 62809 168173 43933 187373 123795 114656 2192 193151 25062 141855 133596 155793 64049 57320 93903 33957 139...
result:
ok correct!
Test #6:
score: 0
Accepted
time: 50ms
memory: 17872kb
input:
200000 1 91999 92900 195726 58991 132067 99937 168188 152017 188495 19779 105961 45241 53406 75757 85118 170259 46250 47585 132248 8609 195110 32777 164307 95643 133411 739 170952 145623 19297 14414 171045 97619 74663 193421 139543 189434 36319 56453 77520 91164 91469 30021 128798 62259 183807 15271...
output:
9098893435 13 1 164355 56677 150505 174723 115829 88068 105453 199874 190131 165416 182628 114943
result:
ok correct!
Test #7:
score: 0
Accepted
time: 38ms
memory: 17848kb
input:
200000 1 189797 1 1 148138 1 95067 141831 1 168151 1 1 25692 95612 1 1 135979 1 141581 119622 1 1 131946 86508 1 98799 1 1 189104 1 117526 46338 1 1 166375 1 28026 165221 1 54204 1 1 98743 1 181414 1 34313 1 71302 1 161200 1 146339 1 47014 1 137258 1 57857 1 196493 1 99105 54487 1 104725 1 1 45203 1...
output:
1175349557 2 1 153544
result:
ok correct!
Test #8:
score: 0
Accepted
time: 70ms
memory: 17456kb
input:
199999 1 56367 178046 1 156890 170478 1 111308 177326 1 188427 1 90169 126610 1 161930 167698 96500 126424 118330 158517 186608 1 95505 107863 1 142887 72279 27494 1 114700 118535 1 68584 63156 97555 19966 39239 1 128030 1 1 86200 66974 1 34616 47100 173578 1 1 117279 89769 43412 1 89670 103573 1 13...
output:
2999144210 3 1 52552 129910
result:
ok correct!
Test #9:
score: 0
Accepted
time: 127ms
memory: 34660kb
input:
200000 1 95601 67789 174512 65854 198542 123861 153390 92355 141969 168754 177054 101194 25665 15524 131869 168080 171051 30732 97293 119758 103002 59019 141990 124310 161550 116618 2585 170410 132999 38200 99202 98733 73949 155033 144918 64086 1594 34916 37138 165382 13452 170885 136973 62178 15250...
output:
200000000000000 200000 1 47213 179780 132180 145558 41335 179095 156350 24912 104386 94658 54370 97034 108043 73905 141018 157563 199841 176455 147422 87545 190562 135095 24903 62484 36389 156106 45144 120321 4911 173474 102976 13602 68252 7332 141515 59337 182112 124040 38089 15458 161370 41901 144...
result:
ok correct!
Test #10:
score: 0
Accepted
time: 82ms
memory: 25812kb
input:
200000 1 122636 169264 76896 89915 72116 125306 186356 74852 84394 177419 21725 144848 106395 111991 189102 195804 6151 170169 185460 146764 6304 149801 147880 99539 6202 175326 104277 26515 39402 33436 116555 185545 44341 92305 197925 125286 28215 102176 182103 160554 105237 169007 105618 75618 190...
output:
49951940813408 100001 1 88700 18534 14218 21693 84470 150823 121376 192964 139616 11067 93019 188349 55336 13628 87630 31553 28945 29827 140175 179655 10038 38915 99968 89953 72978 102045 45280 176852 171879 100086 93399 183932 84482 111738 112608 136016 101850 19371 96135 54333 95939 2865 140685 13...
result:
ok correct!
Test #11:
score: 0
Accepted
time: 40ms
memory: 17092kb
input:
200000 1 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54...
output:
13954593167 18 1 2 5 10 20 40 80 161 323 647 1295 2590 5181 10363 20727 41454 82908 165817
result:
ok correct!
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 7
Accepted
time: 0ms
memory: 3568kb
input:
2 2 2 1 243296356 635616793
output:
878913149 2 1 2
result:
ok correct!
Test #13:
score: -7
Wrong Answer
time: 0ms
memory: 3660kb
input:
10 2 6 4 3 7 5 10 6 10 8 2 3 9 3 5 4 2 1 4 2 4 2 5 5 4 2 3 4 2
output:
33 10 1 4 6 5 9 7 3 10 2 8
result:
wrong answer dist(10, 2) = 3 > k = 2
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #83:
score: 0
Wrong Answer
time: 1ms
memory: 3800kb
input:
2000 3 1359 90 1703 163 158 188 360 1501 195 664 1414 215 1546 1756 536 1096 1726 1223 1150 104 1757 703 1982 282 1023 998 1180 419 576 1759 1496 1993 44 670 1703 952 855 849 1998 1399 1280 980 1533 1090 1270 678 1680 387 469 1734 1799 263 473 588 303 226 5 295 1489 1471 1094 1667 1912 210 1368 1360...
output:
result:
wrong output format Unexpected end of file - int64 expected
Subtask #6:
score: 0
Skipped
Dependency #5:
0%