Submission #1163795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163795		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[2][N], ep[2][N];
vector<pair<int, int>> adj[N];

void dfs(int curr, int prev) {
    int mx1=-INF, mx2=-INF, sum=0, mx3=-INF, mx4=-INF, mx5=-INF;
    vector<int> vec;
    for(auto [next, w]:adj[curr]) if(next!=prev) {
        pw[next]=w, dfs(next, curr);
        dp[0][curr]+=max(dp[0][next], ep[0][next]);
        ep[0][curr]+=max(dp[0][next], ep[0][next]);
        if(dp[0][next]>=ep[0][next]) mx1=max(mx1, w);
        else mx1=max(mx1, dp[0][next]+w-ep[0][next]);
        ep[1][curr]+=max({dp[0][next], dp[1][next], ep[0][next], ep[1][next]});
        if(max(dp[0][next], dp[1][next])>=ep[0][next]) mx2=max(mx2, w);
        else mx2=max(mx2, max(dp[0][next], dp[1][next])+w-max(ep[0][next], ep[1][next]));
        sum+=max(dp[0][next], ep[0][next]);
        if(dp[0][next]>=ep[0][next]) {
            if(mx3<w) mx4=mx3, mx3=w;
            else if(mx4<w) mx4=w;
        }
        else {
            if(mx3<dp[0][next]+w-ep[0][next]) mx4=mx3, mx3=dp[0][next]+w-ep[0][next];
            else if(mx4<dp[0][next]+w-ep[0][next]) mx4=dp[0][next]+w-ep[0][next];
        }
        vec.push_back(mx3);
    }
    ep[0][curr]+=mx1+pw[curr], ep[1][curr]+=mx2+pw[curr];
    dp[1][curr]=sum+mx3+mx4;
    reverse(adj[curr].begin(), adj[curr].end());
    int p=vec.size()-1;
    for(auto [next, w]:adj[curr]) if(next!=prev) {
        dp[1][curr]=max(dp[1][curr], sum-max(dp[0][next], ep[0][next])+dp[1][next]+w+max(mx5, p?vec[--p]:-INF));
        if(dp[0][next]>=ep[0][next]) mx5=max(mx5, w);
        else mx5=max(mx5, dp[0][next]+w-ep[0][next]);
    }
}

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});
    }
    dfs(1, 0);
    cout<<max(dp[0][1], dp[1][1]);
    return 0;
}

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