QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812122#277. Beads and wiresStarrykiller0 16ms10892kbC++232.2kb2024-12-13 11:41:242024-12-13 11:41:25

Judging History

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

  • [2024-12-13 11:41:25]
  • 评测
  • 测评结果:0
  • 用时:16ms
  • 内存:10892kb
  • [2024-12-13 11:41:24]
  • 提交

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, inf=1e9;

vector<pair<int,int>> g[MAXN]; int n;
int f[MAXN][2][2][2], T[2][2][2];

void dfs(int u, int fa) {
    auto S=f[u]; 
    memset(f[u],0xcf,sizeof(f[u]));
    // cerr<<f[u][0][0][0]<<'\n';
    f[u][0][0][0]=0;
    for (const auto& [v,w]: g[u]) if (v!=fa) {
        dfs(v,u);
        auto G=f[v];
        memset(T,0xcf,sizeof(T)); T[0][0][0]=0;
        // no arrow
        for (auto i: {0,1})
        for (auto j: {0,1})
        for (auto k: {0,1})
            T[i][j][k]=S[i][j][k]+max(G[0][0][0],G[1][0][0]);
        
        // 加入一条 v->u 的链
        chmax(T[1][0][1],S[0][0][0]+max(G[0][0][0],G[1][0][0])+w); // 不配对
        chmax(T[1][0][0],S[0][1][0]+max(G[0][0][0],G[1][0][0])+w); // 与一条 u->w 的链配对

        // 加入一条 u->v 的链
        for (auto i: {0,1})
            chmax(T[i][1][0],S[i][0][0]+G[0][0][0]+w), // 不配对
            chmax(T[i][0][0],S[i][0][1]+G[0][0][0]+w); // 与一条 w->u 的链配对

        // 加入一条 u->v 的链,并与 v->w 的链连起来
        for (auto i: {0,1})
        for (auto j: {0,1})
        for (auto k: {0,1})
        chmax(T[i][j][k],S[i][j][k]+G[0][1][0]+w);

        for (auto i: {0,1})
        for (auto j: {0,1})
        for (auto k: {0,1})
            S[i][j][k]=T[i][j][k];
    }
}


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);
    }
    // if (n>10000) return 0;
    int ans=0;
    dfs(1,0);
    ans=max(f[1][0][0][0],f[1][1][0][0]);
    // for (int root=1; root<=n; ++root) {
    //     // int root=1;
    //     dfs(root,0);
    //     chmax(ans,max(f[root][0][0][0],f[root][1][0][0]));
    // }
    cout<<ans<<'\n';

}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

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

output:

60

result:

ok single line: '60'

Test #2:

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

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:

140

result:

ok single line: '140'

Test #3:

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

input:

10
4 10 5
1 10 7
3 10 10
3 9 10
2 3 5
3 8 9
7 10 3
5 8 9
4 6 6

output:

59

result:

wrong answer 1st lines differ - expected: '61', found: '59'

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 15
Accepted
time: 1ms
memory: 5760kb

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:

441

result:

ok single line: '441'

Test #14:

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

input:

100
38 97 8
26 29 9
62 73 7
13 62 8
6 63 3
22 82 9
57 90 10
34 40 10
86 87 6
62 72 8
35 67 4
24 47 10
14 60 9
43 92 4
85 91 1
56 62 5
57 69 6
30 45 8
69 92 5
15 99 1
6 78 9
64 89 1
20 88 8
66 92 2
31 63 4
31 70 8
42 79 2
11 59 2
9 97 6
24 62 8
8 21 9
84 100 7
4 50 10
54 63 5
24 98 10
2 97 1
4 25 3
2...

output:

501

result:

wrong answer 1st lines differ - expected: '498', found: '501'

Subtask #3:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 2ms
memory: 7932kb

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:

3856257

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #32:

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

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:

38571849

result:

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