Submission #1163769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163769		byunjaewoo	Beads and wires (APIO14_beads)	C++20	0 / 100	2 ms	4936 KiB

beads

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

const int N=200010, INF=1e15;
int n, pw[N], dp[N], ep[N];
vector<pair<int, int>> adj[N];

void dfs(int curr, int prev) {
    int sum=0;
    int mx1=-INF, mx2=-INF, mx3=-INF, mx4=-INF, mx5=-INF, mx6=-INF;
    for(auto [next, w]:adj[curr]) if(next!=prev) {
        pw[next]=w, dfs(next, curr);
        sum+=max(dp[next], ep[next]);
        if(dp[next]>=ep[next]) {
            if(mx1<w) mx3=mx2, mx2=mx1, mx1=w;
            else if(mx2<w) mx3=mx2, mx2=w;
            else if(mx3<w) mx3=w;
        }
        else {
            if(mx4<dp[next]+w-ep[next]) mx6=mx5, mx5=mx4, mx4=dp[next]+w-ep[next];
            else if(mx5<dp[next]+w-ep[next]) mx6=mx5, mx5=dp[next]+w-ep[next];
            else if(mx6<dp[next]+w-ep[next]) mx6=dp[next]+w-ep[next];
        }
    }
    dp[curr]=max({sum, sum+mx1+mx2, sum+mx1+mx4, sum+mx4+mx5});
    ep[curr]=max(sum+mx1, sum+mx4)+pw[curr];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++) {
        int u, v, w; cin>>u>>v>>w;
        adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    fill(dp+1, dp+n+1, -INF), fill(ep+1, ep+n+1, -INF);
    dfs(1, 0);
    cout<<dp[1];
    return 0;
}

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