Submission #697269

#	Time	Username	Problem	Language	Result	Execution time	Memory
697269		vjudge1	Beads and wires (APIO14_beads)	C++17	100 / 100	84 ms	28668 KiB

beads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }

const int maxn = 2e5 + 10;
int n, a[maxn];
struct Edge {
    int v, w, nxt;
} e[maxn << 1];
int h[maxn], cnt_e;
void add(int x, int y, int z) { e[++cnt_e] = {y, z, h[x]}, h[x] = cnt_e; }

pll mg(pll u, pll v, int w) {
    return {u.fir + max(v.fir, v.sec + w),
        max(u.sec + max(v.fir, v.sec + w), u.fir + v.fir + w)};
}
pll f[maxn], upf[maxn];
void dfs(int u, int pre) {
    f[u] = {0, -1e18};
    for (int j = h[u]; j; j = e[j].nxt) {
        int v = e[j].v, w = e[j].w;
        if (v == pre) continue;
        a[v] = w, dfs(v, u), f[u] = mg(f[u], f[v], w);
    }
}

pll pr[maxn], sf[maxn];
void dfs2(int u, int pre) {
    vector <pll> son;
    for (int j = h[u]; j; j = e[j].nxt) {
        int v = e[j].v, w = e[j].w;
        if (v == pre) continue;
        son.push_back({v, w});
    }
    int len = son.size();
    pr[0] = sf[len + 1] = {0, -1e18};
    for (int i = 1; i <= len; ++i) pr[i] = mg(pr[i - 1], f[son[i - 1].fir], son[i - 1].sec);
    for (int i = len; i >= 1; --i) sf[i] = mg(sf[i + 1], f[son[i - 1].fir], son[i - 1].sec);
    for (int i = 1; i <= len; ++i) {
        int v = son[i - 1].fir;
        upf[v] = {pr[i - 1].fir + sf[i + 1].fir,
            max(pr[i - 1].sec + sf[i + 1].fir, pr[i - 1].fir + sf[i + 1].sec)};
        upf[v] = mg(upf[v], upf[u], a[u]);
    }
    f[u] = mg(pr[len], upf[u], a[u]);
    for (pll p : son) dfs2(p.fir, u);
}

int main() {
    read(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w; read(u, v, w);
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0), a[1] = -1e9, upf[1] = {0, -1e18}, dfs2(1, 0);
    ll ans = -1e18;
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i].fir);
    write(ans, '\n');
    return 0;
}

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