Submission #258958

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

beads

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

const int N = 2e5;
vector<pair<int, int>> adj[N];
int dp1[N], dp2[N], n;

void dfs(int v, int p = -1) {
    vector<int> v1, v2, v3;
    int ans = 0, delta = -1e18;

    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        dfs(i.first, v);
        v1.push_back(dp1[i.first]);
        v2.push_back(dp2[i.first] + i.second);

        ans += max(v1.back(), v2.back());
        if (v1.back() >= v2.back())
            v3.push_back(i.second);
        else
            v3.push_back(dp1[i.first] - dp2[i.first]);
    }

    dp1[v] = ans;
    sort(v3.begin(),v3.end(), greater<>());
    if (v3.size() >= 2 && v3[0] + v3[1] > 0)
        dp1[v] += v3[0] + v3[1];

    dp2[v] = ans + (v3.empty() ? -1e18 : v3[0]);
}

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    dfs(0);
    cout << dp1[0];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:11:18: warning: unused variable 'delta' [-Wunused-variable]
     int ans = 0, delta = -1e18;
                  ^~~~~
beads.cpp: In function 'long long int solveTestCase()':
beads.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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