Submission #124621

#	Time	Username	Problem	Language	Result	Execution time	Memory
124621		jakob_nogler	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int N = 200005;
const int inf = numeric_limits<int>::max();

vpii t[N];
int n, a, b, w;
int dp[N][3]; // first is without and closed, second is without and opened and third is with

void dfs(int v, int f, int val){
    int sum = 0, mx0 = - inf, mx1 = - inf;

    for(auto u : t[v])
        if(u.fi != f){
            dfs(u.fi, v, u.se);
            int curr = max(dp[u.fi][1], dp[u.fi][2]);
            int temp = max(dp[u.fi][0], dp[u.fi][1]);
            sum += curr;
            if(u.se - curr + temp > mx0)
                mx1 = mx0, mx0 = u.se - curr + temp;
            else if(u.se - curr + temp > mx1)
                mx1 = u.se - curr + temp;
        }

    dp[v][1] = sum;
    if(mx1 != - inf) dp[v][0] = max(mx1 + mx0, 0) + sum;
    if(mx0 != - inf && f != - 1) dp[v][2] = sum + mx0 + val;
    //cout << v << ": " << dp[v][0] << " " << dp[v][1] << " " << dp[v][2] << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b >> w;
        t[a - 1].push_back({b - 1, w});
        t[b - 1].push_back({a - 1, w});
    }

    dfs(0, - 1, 0);
    cout << max(dp[0][0], dp[0][1]) << endl;
}

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