QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811935#277. Beads and wiresStarrykiller0 16ms9316kbC++231.3kb2024-12-13 09:18:542024-12-13 09:18:57

Judging History

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

  • [2024-12-13 09:18:57]
  • 评测
  • 测评结果:0
  • 用时:16ms
  • 内存:9316kb
  • [2024-12-13 09:18:54]
  • 提交

answer

// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }

constexpr int MAXN=2e5+10;

vector<pair<int,int>> g[MAXN]; int n;
int f[MAXN][4], tmp[4];

void dfs(int u, int fa) {
    for (const auto& [v,w]: g[u]) if (v!=fa) {
        dfs(v,u);
        fill(tmp,tmp+4,0);
        chmax(tmp[0],f[u][0]+max(f[v][0],f[v][2]));
        chmax(tmp[1],f[u][1]+max(f[v][0],f[v][2]));
        chmax(tmp[2],f[u][2]+max(f[v][0],f[v][2]));
        chmax(tmp[3],f[u][3]+max(f[v][0],f[v][2]));

        chmax(tmp[1],f[u][0]+max(f[v][0],f[v][2])+w);
        chmax(tmp[2],f[u][1]+max(f[v][1],f[v][3])+w);
        chmax(tmp[3],f[u][0]+max(f[v][0],f[v][2])+w);

        copy(tmp,tmp+4,f[u]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    for (int i=1,u,v,w; i<n; ++i) {
        cin>>u>>v>>w;
        g[u].emplace_back(v,w);
        g[v].emplace_back(u,w);
    }
    int root=3;
    dfs(root,0);
    cout<<max(f[root][0],f[root][2])<<'\n';

}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 13
Accepted
time: 1ms
memory: 5620kb

input:

5
1 2 10
1 3 40
1 4 15
1 5 20

output:

60

result:

ok single line: '60'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 5688kb

input:

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

output:

128

result:

wrong answer 1st lines differ - expected: '140', found: '128'

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 1ms
memory: 5704kb

input:

100
48 93 4
12 87 1
27 72 10
3 43 2
33 86 2
37 80 8
51 98 4
34 57 3
5 51 7
15 100 9
41 72 4
14 30 10
27 80 7
50 71 7
6 77 6
36 66 1
47 61 2
71 92 7
20 94 7
3 59 1
55 69 7
16 33 5
71 79 6
18 96 4
4 43 3
1 55 4
65 75 10
82 96 2
30 74 9
12 19 6
46 93 1
83 94 9
22 24 1
27 51 9
33 92 4
25 42 10
71 81 8
3...

output:

394

result:

wrong answer 1st lines differ - expected: '441', found: '394'

Subtask #3:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 0ms
memory: 5932kb

input:

5000
2198 4992 964
2521 2711 961
3408 4585 975
2746 3304 974
2514 3411 972
602 4079 952
1193 3742 996
774 4530 942
2234 3877 905
346 1537 959
886 3841 937
3126 3342 938
211 2423 977
1725 4740 944
2125 4020 961
1235 3070 903
3109 4669 970
3923 4815 972
2525 4784 979
1159 1511 968
1900 3573 960
2087 2...

output:

3432224

result:

wrong answer 1st lines differ - expected: '3848169', found: '3432224'

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 16ms
memory: 9316kb

input:

50000
22758 25880 990
917 25140 901
10537 30620 913
10368 14209 993
40077 48077 900
5064 20728 937
39641 39844 906
819 11079 965
12203 41474 993
13965 27792 923
20713 39385 991
4266 46545 938
27293 40442 937
12696 27693 961
10394 24153 998
24393 26653 926
25825 32799 963
33049 38343 946
15252 41731 ...

output:

34185277

result:

wrong answer 1st lines differ - expected: '38479584', found: '34185277'