QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117721#6629. Travelling Tradersomethingnew#0 1ms3716kbC++232.5kb2023-07-02 00:28:422024-05-31 18:47:07

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 18:47:07]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3716kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 00:28:42]
  • 提交

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%