Submission #1129410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129410		Hamed_Ghaffari	Beads and wires (APIO14_beads)	C++20	100 / 100	121 ms	28848 KiB

beads

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

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))
#define mins(a, b) (a = min(a,b))
#define Mp make_pair
#define mid ((l+r)>>1)

const int MXN = 2e5+1;
const int INF = 1e9;

int n;
ll dp00[MXN], dp01[MXN], dp10[MXN], dp11[MXN];
ll p0[MXN], p1[MXN], s0[MXN], s1[MXN];
vector<pii> g[MXN];

void dfs(int v, int p=0) {
    vector<pii> ch;
    for(auto [u, w] : g[v]) if(u != p)
        dfs(u, v),
        ch.pb(Mp(u,w));
    int sz = SZ(ch);
    dp01[v] = -INF; dp10[v] = -INF; dp11[v] = -INF;
    for(auto [u, w] : ch)
        dp00[v] += max(dp00[u], dp10[u]+w);
    dp01[v] = dp00[v];
    for(auto [u, w] : ch) {
        ll val = dp00[v]-max(dp00[u], dp10[u]+w);
        maxs(dp01[v], val+max(dp01[u], dp11[u]+w));
        maxs(dp10[v], val+dp00[u]+w);
        maxs(dp11[v], val+max(dp00[u],dp01[u])+w);
    }
    maxs(dp11[v], dp10[v]);
    if(sz<=1) {
        if(sz==0) {
            dp00[v] = dp01[v] = 0;
            dp10[v] = dp11[v] = -INF;
        }
        return;
    }
    fill(p0, p0+sz, 0);
    fill(p1, p1+sz, 0);
    fill(s0, s0+sz, 0);
    fill(s1, s1+sz, 0);
    for(int i=0; i<sz; i++) {
        auto [u, w] = ch[i];
        ll val = max(dp00[u], dp10[u]+w);
        if(i==0) {
            p0[i] += val;
            p1[i] += dp00[u]+w;
        }
        else {
            p0[i] = p0[i-1]; p1[i] = p1[i-1];
            p0[i] += val;
            p1[i] = max(p0[i-1]+dp00[u]+w, p1[i-1]+val);
        }
    }
    for(int i=sz-1; i>=0; i--) {
        auto [u, w] = ch[i];
        ll val = max(dp00[u], dp10[u]+w);
        if(i==sz-1) {
            s0[i] += val;
            s1[i] += dp00[u]+w;
        }
        else {
            s0[i] = s0[i+1]; s1[i] = s1[i+1];
            s0[i] += val;
            s1[i] = max(s0[i+1]+dp00[u]+w, s1[i+1]+val);
        }
    }
    for(int i=0; i<sz; i++) {
        auto [u, w] = ch[i];
        if(i==0)
            maxs(dp01[v], dp01[u]+w+s1[i+1]);
        else if(i==sz-1)
            maxs(dp01[v], dp01[u]+w+p1[i-1]);
        else
            maxs(dp01[v], dp01[u]+w+max(p0[i-1]+s1[i+1], p1[i-1]+s0[i+1]));
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i=0,u,v,w; i<n-1; i++) {
        cin >> u >> v >> w;
        g[u].pb(Mp(v,w));
        g[v].pb(Mp(u,w));
    }

    dfs(1);
    cout << max(dp00[1], dp01[1]) << '\n';

    return 0;
}

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