Submission #558040

#	Time	Username	Problem	Language	Result	Execution time	Memory
558040		hoanghq2004	Beads and wires (APIO14_beads)	C++14	100 / 100	198 ms	25724 KiB

beads

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

int n;
vector <pair <int, int> > e[N];
int f[N][2], _w[N], g[N][2];

void down(int u, int p) {
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        down(v, u);
    }
    int cur[2] = {0, (int)-1e9};
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        _w[v] = w;
        int ncur[2] = {0, (int)-1e9};
        for (int i = 0; i < 2; ++i) {
            ncur[i] = max(ncur[i], cur[i] + max(f[v][0], f[v][1] + w));
            if (i + 1 < 2) ncur[i + 1] = max(ncur[i + 1], cur[i] + f[v][0] + w);
        }
        for (int i = 0; i < 2; ++i) cur[i] = ncur[i];
    }
    f[u][0] = cur[0];
    f[u][1] = cur[1];
}

int child[N];
int c[N];
int prf[N][2], suf[N][2];

void up(int u, int p) {
    int m = 0;
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        child[++m] = v;
        c[m] = w;
    }
    prf[0][0] = 0;
    prf[0][1] = -1e9;
    for (int i = 1; i <= m; ++i) {
        int v = child[i];
        int w = c[i];
        prf[i][0] = prf[i - 1][0] + max(f[v][0], f[v][1] + w);
        prf[i][1] = prf[i - 1][1] + max(f[v][0], f[v][1] + w);
        prf[i][1] = max(prf[i][1], prf[i - 1][0] + f[v][0] + w);
    }
    suf[m + 1][0] = 0;
    suf[m + 1][1] = -1e9;
    for (int i = m; i >= 1; --i) {
        int v = child[i];
        int w = c[i];
        suf[i][0] = suf[i + 1][0] + max(f[v][0], f[v][1] + w);
        suf[i][1] = suf[i + 1][1] + max(f[v][0], f[v][1] + w);
        suf[i][1] = max(suf[i][1], suf[i + 1][0] + f[v][0] + w);
    }
    for (int i = 1; i <= m; ++i) {
        int v = child[i];
        g[v][0] = prf[i - 1][0] + suf[i + 1][0] + max(g[u][0], g[u][1] + _w[u]);
        g[v][1] = max({prf[i - 1][0] + suf[i + 1][1] + max(g[u][0], g[u][1] + _w[u]), prf[i - 1][1] + suf[i + 1][0] + max(g[u][0], g[u][1] + _w[u])});
        if (u != 1) g[v][1] = max(g[v][1], prf[i - 1][0] + suf[i + 1][0] + g[u][0] + _w[u]);
    }
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        up(v, u);
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    down(1, 0);
    g[1][0] = 0, g[1][1] = -1e9;
    up(1, 0);
    int ans = 0;
    for (int r = 1; r <= n; ++r) {
        ans = max(ans, f[r][0] + max(g[r][0], g[r][1] + _w[r]));
    }
    cout << ans;
}

Compilation message (stderr)

beads.cpp: In function 'void down(int, int)':
beads.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for (auto [v, w]: e[u]) {
      |               ^
beads.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for (auto [v, w]: e[u]) {
      |               ^
beads.cpp: In function 'void up(int, int)':
beads.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto [v, w]: e[u]) {
      |               ^
beads.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for (auto [v, w]: e[u]) {
      |               ^

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