QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117957 | #6629. Travelling Trader | valerikk# | 0 | 4ms | 12416kb | C++17 | 2.9kb | 2023-07-02 17:56:16 | 2024-05-31 18:47:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const ll INF = 2e18;
int n, k;
vector<int> g[N];
int a[N];
ll dp[N], dpret[N];
void dfs(int v, int p = -1) {
if (p != -1) {
g[v].erase(find(g[v].begin(), g[v].end(), p));
}
for (int u : g[v]) {
dfs(u, v);
}
ll sum = 0;
for (int u : g[v]) {
sum += a[u];
}
{
dp[v] = a[v];
for (int u : g[v]) {
dp[v] = max(dp[v], a[v] + dp[u] - a[u] + sum);
dp[v] = max(dp[v], a[v] + dpret[u] - a[u] + sum);
}
for (int u : g[v]) {
for (int w : g[v]) {
if (u != w) {
dp[v] = max(dp[v], a[v] + dp[u] - a[u] + dpret[w] - a[w] + sum);
}
}
}
}
{
dpret[v] = a[v] + sum;
for (int u : g[v]) {
dpret[v] = max(dpret[v], a[v] + dpret[u] - a[u] + sum);
}
}
}
vector<int> getordret(int v) {
ll sum = 0;
for (int u : g[v]) {
sum += a[u];
}
if (dpret[v] == a[v] + sum) {
vector<int> ord = {v};
for (int u : g[v]) {
ord.push_back(u);
}
return ord;
}
for (int u : g[v]) {
if (dpret[v] == a[v] + dpret[u] - a[u] + sum) {
vector<int> ord = {v};
auto ordu = getordret(u);
reverse(ordu.begin(), ordu.end());
for (int w : ordu) {
ord.push_back(w);
}
for (int w : g[v]) {
if (w != u) {
ord.push_back(w);
}
}
return ord;
}
}
assert(0);
return {v};
}
vector<int> getord(int v) {
ll sum = 0;
for (int u : g[v]) {
sum += a[u];
}
if (dp[v] == a[v]) {
return {v};
}
for (int u : g[v]) {
if (dp[v] == a[v] + dp[u] - a[u] + sum) {
vector<int> ord = {v};
for (int w : g[v]) {
if (w != u) {
ord.push_back(w);
}
}
auto ordu = getord(u);
for (int w : ordu) {
ord.push_back(w);
}
return ord;
}
if (dp[v] == a[v] + dpret[u] - a[u] + sum) {
vector<int> ord = {v};
auto ordu = getordret(u);
reverse(ordu.begin(), ordu.end());
for (int w : ordu) {
ord.push_back(w);
}
for (int w : g[v]) {
if (w != u) {
ord.push_back(w);
}
}
return ord;
}
for (int w : g[v]) {
if (dp[v] == a[v] + dp[u] - a[u] + dpret[w] - a[w] + sum) {
vector<int> ord = {v};
auto ordu = getord(u);
auto ordw = getordret(w);
reverse(ordw.begin(), ordw.end());
for (int l : ordw) {
ord.push_back(l);
}
for (int l : g[v]) {
if (l != u && l != w) {
ord.push_back(l);
}
}
for (int l : ordu) {
ord.push_back(l);
}
return ord;
}
}
}
assert(0);
return {v};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 0; i < n - 1; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
dfs(0);
ll ans = max(dp[0], dpret[0]);
vector<int> ord;
if (ans == dp[0]) {
ord = getord(0);
} else {
ord = getordret(0);
}
cout << ans << "\n";
cout << ord.size() << "\n";
for (int v : ord) {
cout << v + 1 << " ";
}
cout << "\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 2
Accepted
time: 0ms
memory: 11392kb
input:
2 1 1 2 255959470 961356354
output:
1217315824 2 1 2
result:
ok correct!
Test #2:
score: -2
Wrong Answer
time: 2ms
memory: 12056kb
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:
1370702 268 1 929 264 819 173 273 641 858 902 391 704 961 418 471 392 642 728 654 283 656 511 449 548 622 542 169 368 896 694 472 605 685 393 691 921 540 505 470 185 874 103 778 824 89 69 437 358 202 747 396 750 222 144 42 106 467 569 193 975 13 551 289 344 518 959 587 114 857 803 731 768 108 238 81...
result:
wrong answer dist(1, 929) = 2 > k = 1
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 7
Accepted
time: 2ms
memory: 10376kb
input:
2 2 2 1 243296356 635616793
output:
878913149 2 1 2
result:
ok correct!
Test #13:
score: 0
Accepted
time: 2ms
memory: 11848kb
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 8 2 6 10 5 3 9 7
result:
ok correct!
Test #14:
score: -7
Wrong Answer
time: 0ms
memory: 11540kb
input:
200 2 150 170 21 33 96 152 143 26 136 70 92 159 34 164 163 182 74 115 93 61 151 83 81 119 10 146 114 170 39 83 139 4 173 41 193 96 87 57 14 164 107 51 45 15 157 17 43 183 96 30 11 137 55 18 138 81 87 12 112 122 159 82 195 185 75 71 16 191 33 88 70 195 149 114 106 160 96 118 92 44 9 141 107 143 151 2...
output:
54153356810 91 1 151 179 194 89 83 135 27 122 117 120 180 125 112 40 45 138 94 162 88 21 193 59 170 149 110 28 171 114 96 105 131 33 15 99 72 12 76 70 53 159 17 178 24 44 41 67 173 186 42 116 92 82 197 101 5 32 121 87 29 198 64 93 19 126 8 141 37 100 3 9 108 52 61 54 14 137 49 26 165 47 50 148 75 12...
result:
wrong answer your profit is 54153356810 but jury's plan is 57921623677, your plan is not optimal!
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: 4
Accepted
time: 3ms
memory: 12416kb
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:
1008611451196 2000 1 1091 961 605 1613 454 1237 1823 1101 1617 1369 1840 562 1256 901 1040 709 1291 1238 1526 129 523 816 1919 674 1961 452 297 1903 1656 560 739 183 1522 951 863 877 1973 1548 191 1265 1344 33 1679 565 774 276 139 926 1397 46 36 1019 1427 289 1376 545 16 1880 1076 1684 1968 1504 81 ...
result:
ok correct!
Test #84:
score: 0
Accepted
time: 4ms
memory: 11508kb
input:
2000 3 1727 567 1783 1850 205 985 323 1094 1153 821 1756 117 377 1928 1026 1303 1343 1814 268 745 242 948 1140 1218 7 1675 101 1798 1403 1752 1184 671 87 248 1953 30 1580 1441 507 1438 525 419 901 421 1585 1405 1575 883 1952 1930 1988 1325 615 722 994 1202 178 474 1978 1500 899 481 216 409 999 1817 ...
output:
1012330476243 2000 1 369 1789 598 488 422 419 525 269 202 1079 694 1379 1724 1454 1545 88 1123 246 701 1522 1158 1696 1364 1918 131 1589 1832 872 1532 1057 345 1725 67 761 1634 1174 719 1807 650 693 61 718 554 841 1935 234 175 220 105 917 1784 997 1315 1530 92 257 1071 802 1369 1257 1046 1275 993 31...
result:
ok correct!
Test #85:
score: -4
Wrong Answer
time: 3ms
memory: 11444kb
input:
2000 3 1213 130 101 508 72 1199 1550 1096 1099 861 1515 627 1299 1672 1338 105 1444 1019 15 1560 1949 971 52 1312 30 529 186 1687 1917 484 1971 349 537 1223 1955 1377 300 1060 1786 1811 1960 90 1959 1353 1831 1548 303 511 1073 1197 863 1527 1379 994 31 9 1247 1707 1395 1532 29 1544 119 296 1919 1554...
output:
803960409885 1502 1 1365 1487 810 1721 1986 1821 668 513 830 1002 1255 1557 751 574 1658 1802 1491 60 1261 640 374 1010 1292 1450 1710 1896 718 942 1246 706 295 1377 1955 729 954 242 1809 93 1610 381 435 1127 863 384 1356 1067 181 1503 1169 1153 1241 1997 563 1475 1303 1310 1208 388 1069 1483 1181 8...
result:
wrong answer your profit is 803960409885 but jury's plan is 1001405462082, your plan is not optimal!
Subtask #6:
score: 0
Skipped
Dependency #5:
0%