Submission #344534

#	Time	Username	Problem	Language	Result	Execution time	Memory
344534		Sara	Beads and wires (APIO14_beads)	C++14	0 / 100	38 ms	47340 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long int
#define F first
#define S second
#define pb push_back

const ll N = 1e6 + 3;
const ll LOG = 19;
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 5;

int n;
ll dp[3][N], hlp[3][N];
vector < pair <int, ll> > adj[N], g[N];
// dp[0][v] hichi nis
// dp[1][v] markaz yeki az bache ha be baba yeki dige be paiin
// dp[2][v] markaz ha do bache be paiin

int smax(int v){
    return max({dp[0][v], dp[1][v], dp[2][v]});
}
int gmax(int v){
    return max(dp[0][v], dp[2][v]);
}
void dfs(int v = 1, int p = 0, ll w = 0){
    ll sum = 0;
    for (auto i : adj[v]){
        int u = i.F;
        if (u == p) continue;
        g[v].pb(i);
        dfs(u, v, i.S);
        sum += smax(u);
    }

    dp[0][v] = sum; sum += w;

    int sz = g[v].size();
    if (sz < 1 || v == 1) dp[1][v] = -INF;
    else {
        for (auto i : g[v]){
            int u = i.F;
            dp[1][v] = max(dp[1][v], sum - smax(u) + i.S + gmax(u));
        }
    }

    if (sz < 2) dp[2][v] = -INF;
    else {
        int a = g[v][0].F;
        ll wa = g[v][0].S;
        int b = g[v][1].F;
        ll wb = g[v][1].S;
        hlp[0][1] = smax(a) + smax(b);
        hlp[1][1] = max(wa + gmax(a) + smax(b), wb + smax(a) + gmax(b));
        hlp[2][1] = wa + wb + gmax(a) + gmax(b);
        for (int i = 2; i < sz; i ++){
            int u = g[v][i].F;
            ll wei = g[v][i].S;
            hlp[0][i] = hlp[0][i - 1] + smax(u);
            hlp[1][i] = max(hlp[1][i - 1] + smax(u), hlp[0][i - 1] + wei + gmax(u));
            hlp[2][i] = max(hlp[2][i - 1] + smax(u), hlp[1][i - 1] + wei + gmax(u));
        } 
        dp[2][v] = hlp[2][sz - 1];
        for (int i = 0; i < sz; i ++){
            hlp[0][i] = hlp[1][i] = hlp[2][i] = 0;
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dfs();
    cout << max(dp[0][1], dp[2][1]) << '\n';
    return 0;
}

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