Submission #1121269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121269		PagodePaiva	Beads and wires (APIO14_beads)	C++17	0 / 100	7 ms	8272 KiB

beads

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;
vector <pair <int, int>> g[N];
int dp[N][2][2];
const int inf = 2e9;

void dfs(int v, int f1, int f2, int p){
    if(dp[v][f1][f2] != -1) return;
    for(auto [x, w] : g[v]){
        if(x == p) continue;
        dfs(x, 0, 0, v);
        dfs(x, 0, 1, v);
        dfs(x, 1, 0, v);
        dfs(x, 1, 1, v);
    }
    if(f1 == 0 and f2 == 0){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                if(w > best1){
                    best2 = best1;
                    best1 = w;
                }
                else if(w > best2){
                    best2 = w;
                }
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = best1;
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
            else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    if(f1 == 1 and f2 == 0){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                best2 = w;
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf and best1 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    if(f1 == 0 and f2 == 1){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = best1;
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
            else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    dp[v][f1][f2] = 0;
    int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
    for(auto [x, w] : g[v]){
        if(x == p) {
            continue;
        }
        sum += dp[x][0][0];
        sum2 += dp[x][1][0];
        if(best1 < dp[x][1][1]+w-dp[x][1][0]){
            best2 = best1;
            best1 = dp[x][1][1]+w-dp[x][1][0];
        }
        else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
            best2 = dp[x][1][1]+w-dp[x][1][0];
        }
    }
    dp[v][f1][f2] = sum;
    if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
    return;
}

int main(){
    memset(dp, -1, sizeof dp);
    int n;
    cin >> n;
    for(int i = 1;i < n;i++){
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    dfs(1, 0, 1, 1);
    cout << dp[1][0][1] << '\n';
}

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