Submission #699108

#	Time	Username	Problem	Language	Result	Execution time	Memory
699108		Ronin13	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	11988 KiB

beads

#include <bits/stdc++.h>
#define ll long  long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =500001;

/*

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
ll dp[nmax][2][2];
ll val[nmax];

vector <vector <pii> > g(nmax);

void dfs(int v, int e = -1){
    ll mx = -1e9;
    pair<pll, pll> mx1;
    pair<pll, pll> mx2;
    pair<pll, pll> mx3, mx4;
    mx1 = mx2 = mx3 = mx4 = {{mx, mx}, {mx, mx}};
    ll MX = -1e9;
    for(auto ed : g[v]){
        int to = ed.f;
        ll len = ed.s;
        if(to == e) continue;
        val[to] = len;
        dfs(to, v);
        ll y = max(dp[to][1][0], dp[to][0][0]);
        dp[v][0][0] += y;
        mx = max(mx, dp[to][0][0] - y + val[to]);
        ll z = dp[to][0][1] - y + val[to];
        mx1.s = max(mx1.s, {z, to});
        if(mx1.f < mx1.s)
            swap(mx1.f, mx1.s);
        z = dp[to][0][0] - y + val[to];
        mx2.s = max(mx2.s, {z, to});
        if(mx2.f < mx2.s)
            swap(mx2.f, mx2.s);
        MX = max(MX, dp[to][0][1] - y + val[to]);

    }
    dp[v][1][0] = max(dp[v][1][0], mx + dp[v][0][0] + val[v]);
    if(mx1.f.s == mx2.f.s){
        dp[v][0][1] = dp[v][0][0] + max(mx1.f.f + mx2.s.f, mx1.s.f + mx2.f.f);
    }
    else dp[v][0][1] = max(dp[v][0][1], dp[v][0][0] + mx1.f.f + mx2.f.f);
    dp[v][1][1] = dp[v][0][0] + MX;

    dp[v][0][1] = max(dp[v][0][1], dp[v][0][0]);
    dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]);
}

int32_t main() {
    int n; cin >> n;
    val[1] = -1e9;
    for(int i = 1; i < n; i++){
        int u, v, c; cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    dfs(1);
    cout << max(dp[1][0][1], dp[1][0][0]);
}

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