Submission #112592

#	Time	Username	Problem	Language	Result	Execution time	Memory
112592		Akashi	Beads and wires (APIO14_beads)	C++14	100 / 100	222 ms	20584 KiB

beads

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[200005][2][2];
bool f[200005];
vector <pair <int, int> > v[200005];

void dfs(int nod = 1, int TT = 0){
    f[nod] = 1;

    int Sum = 0, Max = -2000000000, Max1 = -2000000000, Max2 = -2000000000;
    for(auto it : v[nod]){
        if(f[it.first]) continue ;
        dfs(it.first, it.second);

        Sum = Sum + max(dp[it.first][0][0], dp[it.first][0][1]);

        Max = max(Max, max(dp[it.first][1][0], dp[it.first][1][1]) - max(dp[it.first][0][0], dp[it.first][0][1]));

        Max1 = max(Max1, dp[it.first][0][0] + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));
        Max2 = max(Max2, dp[it.first][1][0] + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));
    }
    dp[nod][0][0] = max(0, Sum);
    dp[nod][1][0] = max(0, Sum + Max);

    if(nod != 1){
        dp[nod][0][1] = max(0, Sum + Max1 + TT);
        dp[nod][1][1] = max(0, Sum + Max2 + TT);
    }

    Max1 = -2000000000, Max2 = -2000000000;
    for(auto it : v[nod]){
        if(f[it.first]) continue ;

        dp[nod][1][0] = max(dp[nod][1][0], Sum + Max1 + max(dp[it.first][0][0], dp[it.first][1][0]) + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));
        dp[nod][1][0] = max(dp[nod][1][0], Sum + Max2 + dp[it.first][0][0] + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));

        Max1 = max(Max1, dp[it.first][0][0] + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));
        Max2 = max(Max2, dp[it.first][1][0] + it.second - max(dp[it.first][0][0], dp[it.first][0][1]));
    }
    f[nod] = 0;
}

int main()
{
    scanf("%d", &n);
    int x, y, l;
    for(int i = 1; i < n ; ++i){
        scanf("%d%d%d", &x, &y, &l);
        v[x].push_back({y, l});
        v[y].push_back({x, l});
    }

    dfs();
    printf("%d", max(max(dp[1][0][0], dp[1][1][0]), max(dp[1][0][1], dp[1][1][1])));

    return 0;
}
/*
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
*/

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &l);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43