QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812109#277. Beads and wiresStarrykiller13 696ms8072kbC++232.1kb2024-12-13 11:38:282024-12-13 11:38:29

Judging History

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

  • [2024-12-13 11:38:29]
  • 评测
  • 测评结果:13
  • 用时:696ms
  • 内存:8072kb
  • [2024-12-13 11:38:28]
  • 提交

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;
    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';

}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 13
Accepted

Test #1:

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

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: 5632kb

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: 13
Accepted
time: 1ms
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:

61

result:

ok single line: '61'

Test #4:

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

input:

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

output:

30

result:

ok single line: '30'

Test #5:

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

input:

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

output:

44

result:

ok single line: '44'

Test #6:

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

input:

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

output:

62

result:

ok single line: '62'

Test #7:

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

input:

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

output:

41

result:

ok single line: '41'

Test #8:

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

input:

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

output:

53

result:

ok single line: '53'

Test #9:

score: 13
Accepted
time: 0ms
memory: 5704kb

input:

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

output:

43

result:

ok single line: '43'

Test #10:

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

input:

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

output:

39

result:

ok single line: '39'

Test #11:

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

input:

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

output:

48

result:

ok single line: '48'

Test #12:

score: 13
Accepted
time: 0ms
memory: 5704kb

input:

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

output:

35

result:

ok single line: '35'

Subtask #2:

score: 0
Wrong Answer

Test #13:

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

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:

446

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 696ms
memory: 5968kb

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:

3856312

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 13ms
memory: 8072kb

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:


result:

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