Submission #1121204

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

beads

#include<bits/stdc++.h>

using namespace std;

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

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

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, 1, 1);
    cout << dp[1][1] << '\n';
}

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