Submission #1202603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202603		niepamietamhasla	Beads and wires (APIO14_beads)	C++20	100 / 100	75 ms	20476 KiB

beads

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

const int MAXN = 2e5 + 5;
const int MAXINT = 2e9;
vector<pair<int,int>> graf[MAXN];
int dp[MAXN][2];
pair<int,int> gdz[MAXN][2];

int ans = 0;

int dfs1(int v, int p){
    int m = -MAXINT;
    for(auto u : graf[v]){
        if(u.first == p) continue;
        dfs1(u.first, v);
        dp[v][0] += max(dp[u.first][0], dp[u.first][1] + u.second);
        m = max(m, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second));
    }
    dp[v][1] = dp[v][0] + m;
    return 0;
}

void dfs2(int v, int p, int k){
    int m1, m2;
    int k1, k2;
    m1 = m2 = k1 = k2 = -MAXINT;
    if(v != 1){
        int w1, w2;
        w1 = dp[p][0] - max(dp[v][0], dp[v][1] + k);
        if(gdz[p][0].first == v){
            w2 = w1 + gdz[p][1].second;
        }
        else{
            w2 = w1 + gdz[p][0].second;
        }
        int ma = w1 + k - max(w1, w2 + k);
        for(auto u : graf[v]){
            if(u.first == p) continue;
            ma = max(ma, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second));
        }
        m1 = w1 + k - max(w1, w2 + k);
        k1 = p;
        dp[v][0] += max(w1, w2 + k);
        dp[v][1] += max(w1, w2 + k) + ma;
    }
    for(auto u : graf[v]){
        if(u.first == p) continue;
        int c = dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second);
        if(c > m1){
            m2 = m1;
            m1 = c;
            k2 = k1;
            k1 = u.first;
        }
        else if(c > m2){
            m2 = c;
            k2 = u.first;
        }
    }
    ans = max(ans, dp[v][0]);
    gdz[v][0] = {k1, m1};
    gdz[v][1] = {k2, m2};
    for(auto u : graf[v]){
        if(u.first == p) continue;
        dfs2(u.first, v, u.second);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a, b, c;
    for(int i = 0; i < n-1; ++i){
        cin >> a >> b >> c;
        graf[a].push_back({b,c});
        graf[b].push_back({a,c});
    }
    dfs1(1, -1);
    ans = dp[1][0];
    dfs2(1, -1, 0);
    cout << ans << "\n";
    return 0;
}

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