Submission #23719

#	Time	Username	Problem	Language	Result	Execution time	Memory
23719		abcdef6199	Beads and wires (APIO14_beads)	C++98	0 / 100	16 ms	4992 KiB

beads

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

typedef long long LL;
typedef pair<int, int> II;

const int N = (int) 2e5 + 10;
int n, dp[N][2];
vector<II> adj[N];

void DFS(int u, int p = -1) {
    if ((int) adj[u].size() == 1 && adj[u][0].first == p) {
        dp[u][0] = 0;
        dp[u][1] = -2e9;
        return;
    }
    vector<int> delta;
    for (int i = 0; i < (int) adj[u].size(); ++i) {
        int v = adj[u][i].first;
        int w = adj[u][i].second;
        if (v != p) {
            DFS(v, u);
            int f = max(dp[v][0], w + dp[v][1]);
            dp[u][0] += f;
            dp[u][1] += f;
            delta.push_back(w + dp[v][0] - f);
        }
    }
    sort(delta.begin(), delta.end(), greater<int>());
    dp[u][1] += delta[0];
    if (delta.size() >= 2 && delta[0] + delta[1] >= 0) dp[u][0] += delta[0] + delta[1];
}

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    freopen("out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back(II(v, w));
        adj[v].push_back(II(u, w));
    }

    DFS(1);
    printf("%d", dp[1][0]);
    return 0;
}

Compilation message (stderr)

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

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