Submission #34649

#	Time	Username	Problem	Language	Result	Execution time	Memory
34649		nickyrio	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	4992 KiB

beads

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 200100
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
#define bit(S, i) ((S >> i) & 1)
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

int n;
vector<pp> e[N];
long long dp[N][4];

void dfs(int u, int p) {
    REP(i, 3) dp[u][i] = -1e18;
    dp[u][0] = 0;
    for (pp tt : e[u]) if (tt.first != p) {
        int v = tt.first;
        int c = tt.second;
        dfs(v, u);
        //Prepare
        long long t0 = dp[v][0];
        long long t1 = dp[v][1] + c;
        long long t2 = dp[v][2];
        long long add = max(t0, max(t1, t2));
        //
        FORD(i, 2, 0) {
            dp[u][i] += add;
            if (i == 1) dp[u][i] = max(dp[u][i], dp[u][i - 1] + max(t0, t2) + c);
            if (i == 2) dp[u][i] = max(dp[u][i], dp[u][i - 1] + t0 + c);
        }
    }
}

int main() {
    IO;
 //   freopen("input.txt","r",stdin);
 //   freopen("output.txt","w",stdout);
    int u, v, c;
    read(n);
    FOR(i, 2, n) {
        read(u);read(v);read(c);
        e[u].push_back(pp(v, c));
        e[v].push_back(pp(u, c));
    }
    dfs(1, -1);
    writeln(max(dp[1][0], dp[1][2]));
}

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