Submission #50797

#	Time	Username	Problem	Language	Result	Execution time	Memory
50797		waynetuinfor	Beads and wires (APIO14_beads)	C++17	28 / 100	1068 ms	24192 KiB

beads

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

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

void dfs(int x, int p) {
    dp[0][x] = 0; dp[1][x] = dp[2][x] = -inf;
    for (auto u : gr[x]) if (u.first != p) {
        dfs(u.first, x);
        dp[0][x] += max(dp[1][u.first] + u.second, max(dp[2][u.first], dp[0][u.first]));
    }
    for (auto u : gr[x]) if (u.first != p) {
        long long t = max(dp[1][u.first] + u.second, max(dp[2][u.first], dp[0][u.first]));
        dp[1][x] = max(dp[1][x], dp[0][x] - t + u.second + max(dp[2][u.first], dp[0][u.first]));
    }
    /* for (int i = 0; i < gr[x].size(); ++i) if (gr[x][i].first != p) {
        for (int j = 0; j < gr[x].size(); ++j) if (gr[x][j].first != p) {
            int a = gr[x][i].first, b = gr[x][j].first;
            int c = gr[x][i].second, d = gr[x][j].second;
            if (a == b) continue;
            long long y = max(dp[1][a] + c, max(dp[2][a], dp[0][a]));
            long long z = max(dp[1][b] + d, max(dp[2][b], dp[0][b]));
            dp[2][x] = max(dp[2][x], dp[0][x] - y - z + c + max(dp[2][a], dp[0][a]) + d + max(dp[2][b], dp[0][b]));
        }
    } */
}

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);
        gr[a].emplace_back(b, c);
        gr[b].emplace_back(a, c);
    }
    long long ans = -inf;
    for (int i = 1; i <= n; ++i) {
        dfs(i, 0);
        ans = max(ans, dp[0][i]);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:32: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:34: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: 0 / 29
• Subtask 4: 0 / 43