Submission #491205

#	Time	Username	Problem	Language	Result	Execution time	Memory
491205		Saacoota	Beads and wires (APIO14_beads)	C++14	100 / 100	167 ms	19620 KiB

beads

#include <bits/stdc++.h>
#define ii pair < int , int >
#define fi first
#define se second

using namespace std;

const int maxn = 200010;
const int inf = 0x3f3f3f3f;

vector < ii > g[maxn];
int dp[maxn][3] , f[maxn];

void DFS(int u,int p,int wp) {
    for (auto v : g[u])
    if (v.fi != p)
        DFS(v.fi , u , v.se);
    for (auto v : g[u])
    if (v.fi != p)
        dp[u][0] += max(dp[v.fi][0] , dp[v.fi][1]);
    for (auto v : g[u])
    if (v.fi != p)
        dp[u][1] = max(dp[u][1] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][0] + wp + v.se);
    dp[u][2] = dp[u][0];
    int ma1 , ma2;
    ma1 = ma2 = -inf;
    for (auto v : g[u])
    if (v.fi != p) {
        int cur = dp[v.fi][0] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se;
        if (cur > ma1) {
            ma2 = ma1;
            ma1 = cur;
        } else ma2 = max(ma2 , cur);
    }
    for (auto v : g[u])
    if (v.fi != p) {
        int cur = ma1;
        if (cur == dp[v.fi][0] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se) cur = ma2;
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2]);
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2] + cur + v.se);
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + f[v.fi] + v.se);
    }
    f[u] = -inf;
    for (auto v : g[u])
    if (v.fi != p)
        f[u] = max(f[u] , dp[v.fi][2] + v.se + dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1 ; i < n ; ++i) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].emplace_back(v , w);
        g[v].emplace_back(u , w);
    }
    DFS(1 , 0 , 0);
    cout << dp[1][2];
}

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