Submission #699007

#	Time	Username	Problem	Language	Result	Execution time	Memory
699007		Ronin13	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	12064 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;

int dp[nmax][3];
int val[nmax];

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

void dfs(int v, int e = -1){
    pair <pii, pii> mx1, mx2;
    mx1 = {{-1e9, -1e9}, {-1e9, -1e9}};
    mx2 = mx1;
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        int x = ed.s;
        val[to] = x;
        dfs(to, v);
        dp[v][0] += max({dp[to][0], dp[to][1], dp[to][2]});
        int vv = max(dp[to][0], dp[to][2]) - max({dp[to][0], dp[to][1], dp[to][2]}) + val[to];
        int uu = dp[to][0] - max({dp[to][0], dp[to][1], dp[to][2]}) + val[to];
        mx1.s = max(mx1.s, {vv, to});
        mx2.s = max(mx2.s, {uu, to});
        if(mx1.s.f > mx1.f.f)
            swap(mx1.s, mx1.f);
        if(mx2.s.f > mx2.f.f)
            swap(mx2.s, mx2.f);
    }
    dp[v][1] = dp[v][0] + mx1.f.f + val[v];
    if(mx1.f.s == mx2.f.s){
        dp[v][2] = dp[v][0] + mx1.f.f + mx2.s.f;
        dp[v][2] = max(dp[v][2], dp[v][0] + mx1.s.f + mx2.f.f);
    }
    else dp[v][2] = dp[v][0] + mx1.f.f + mx2.f.f;
}

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], dp[1][2]);
}

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