Submission #557882

#	Time	Username	Problem	Language	Result	Execution time	Memory
557882		hoanghq2004	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	5028 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> > g[N];
int f[N][2];

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

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;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    cout << f[1][0] << '\n';
}

Compilation message (stderr)

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

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