QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117721 | #6629. Travelling Trader | somethingnew# | 0 | 1ms | 3716kb | C++23 | 2.5kb | 2023-07-02 00:28:42 | 2024-05-31 18:47:07 |
Judging History
answer
// ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
// ➡ @roadfromroi ⬅
// ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
vector<int> dpdeep;
vector<int> p;
vector<vector<int>> g;
vector<int> road;
void print() {
int res = 0;
for (auto i : road)
res += p[i];
cout << res << '\n' << road.size() << '\n';
for (auto i : road)
cout << i + 1 << ' ';
}
void dfs1(int v, int pr) {
dpdeep[v] = p[v];
for (auto i : g[v]) {
if (i != pr) {
dfs1(i, v);
dpdeep[v] = max(dpdeep[v], dpdeep[i] + p[v]);
}
}
}
void dfs2(int v, int pr) {
road.push_back(v);
int tr = -1;
for (auto i : g[v]) {
if (i != pr) {
if (tr == -1)
tr = i;
if (dpdeep[tr] < dpdeep[i])
tr = i;
}
}
if (tr != -1)
dfs2(tr, pr);
}
void sl1(int n) {
dpdeep.assign(n, {});
dfs1(0, 0);
dfs2(0, 0);
print();
}
vector<int> dfroad;
vector<int> ls;
void dfs3(int v, int pr) {
dfroad.push_back(v);
ls[v] = dfroad.size() - 1;
for (auto i : g[v]) {
if (i == pr)
continue;
dfs3(i, v);
dfroad.push_back(v);
ls[v] = dfroad.size() - 1;
}
}
void sl3(int n) {
ls.assign(n, {});
vector<int> sn(n);
dfs3(0, 0);
int trns = 3;
int pos = 0;
for (auto i : dfroad) {
trns--;
if (trns == 0) {
if (sn[i] == 1)
exit(1);
road.push_back(i);
sn[i] = 1;
trns = 3;
}
if (pos == ls[i] and sn[i] == 0) {
road.push_back(i);
sn[i] = 1;
trns = 3;
}
pos++;
}
print();
}
void solve() {
int n, k;
cin >> n >> k;
p.assign(n, {});
g.assign(n, {});
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;a--;b--;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
if (k == 1)
sl1(n);
if (k == 3)
sl3(n);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
while (t--) {
solve();
}
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 2
Accepted
time: 0ms
memory: 3604kb
input:
2 1 1 2 255959470 961356354
output:
1217315824 2 1 2
result:
ok correct!
Test #2:
score: -2
Time Limit Exceeded
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:
result:
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3556kb
input:
2 2 2 1 243296356 635616793
output:
result:
wrong output format Unexpected end of file - int64 expected
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: 3716kb
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:
-705863364 2000 379 1954 1539 605 1300 1823 1866 1840 867 709 88 916 1526 1238 773 1919 816 1788 832 297 1349 1808 1428 183 863 951 1522 301 775 1265 936 1087 1672 565 1963 1330 926 1325 524 1334 36 46 1231 240 665 1376 289 1427 1319 1076 1880 1668 81 1504 1561 1987 1404 1630 1809 1354 295 1084 743 ...
result:
wrong answer your path must start at vertex 1
Subtask #6:
score: 0
Skipped
Dependency #5:
0%