Submission #50798

#	Time	Username	Problem	Language	Result	Execution time	Memory
50798		waynetuinfor	Beads and wires (APIO14_beads)	C++17	100 / 100	316 ms	39016 KiB

beads

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
const long long inf = 1e15;
vector<pair<int, int>> graf[maxn];
long long dp[2][maxn], ans;

void dfs(int x, int p) {
    dp[0][x] = 0; dp[1][x] = -inf;
    for (auto u : graf[x]) if (u.first != p) {
        dfs(u.first, x);
        dp[0][x] += max(dp[1][u.first] + u.second, dp[0][u.first]);
    }
    for (auto u : graf[x]) if (u.first != p) {
        long long t = max(dp[1][u.first] + u.second, dp[0][u.first]);
        dp[1][x] = max(dp[1][x], dp[0][x] - t + dp[0][u.first] + u.second);
    }
}

void dfsans(int x, int p, long long f, long long t0, long long t1) {
    long long k0 = dp[0][x] + max(t1 + f, t0);
    ans = max(ans, k0);
    pair<long long, int> p1 = make_pair(-inf, -1), p2 = make_pair(-inf, -1);
    for (auto u : graf[x]) if (u.first != p) {
        long long k = max(dp[1][u.first] + u.second, dp[0][u.first]);
        long long c = -k + dp[0][u.first] + u.second;
        pair<long long, int> pt = make_pair(c, u.first);
        if (pt > p1) p2 = p1, p1 = pt;
        else if (pt > p2) p2 = pt;
    }
    for (auto u : graf[x]) if (u.first != p) {
        long long z0 = k0 - max(dp[1][u.first] + u.second, dp[0][u.first]);
        long long z1 = z0 - max(t1 + f, t0) + t0 + f;
        z1 = max(z1, z0 + (p1.second == u.first ? p2.first : p1.first));
        dfsans(u.first, x, u.second, z0, z1);
    }
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        graf[a].emplace_back(b, c);
        graf[b].emplace_back(a, c);
    }
    dfs(1, 0);
    ans = -inf;
    dfsans(1, 0, -inf, 0, -inf);
    printf("%lld%c\n", ans, (char)(13));
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d", &n);
            ~~~~~^~~~~~~~~~
beads.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b, c; scanf("%d %d %d", &a, &b, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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