Submission #145206

#	Time	Username	Problem	Language	Result	Execution time	Memory
145206		dolphingarlic	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	5112 KiB

beads

#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

vector<pair<ll, ll>> graph[200001];
ll dp1[200001], dp2[200001];  // dp2 = is center and goes up

void dfs(ll node, ll parent, ll edge) {
    int best = INT_MIN, second = INT_MIN;
    
    for (pair<ll, ll> i : graph[node]) {
        if (i.first != parent) {
            dfs(i.first, node, i.second);

            dp1[node] += max(dp1[i.first], dp2[i.first]);
        }
    }
    for (pair<ll, ll> i : graph[node]) {
        if (i.first != parent) {
            dp2[node] =
                max(dp2[node], dp1[node] - max(dp1[i.first], dp2[i.first]) + dp1[i.first] + i.second + edge);

            if (dp1[i.first] + i.second - max(dp1[i.first], dp2[i.first]) > best) {
                second = best;
                best = dp1[i.first] + i.second - max(dp1[i.first], dp2[i.first]);
            } else if (dp1[i.first] + i.second - max(dp1[i.first], dp2[i.first]) > second) {
                second = dp1[i.first] + i.second - max(dp1[i.first], dp2[i.first]);
            }
        }
    }

    if (best + second > 0) dp1[node] += best + second;
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    FOR(i, 1, n) {
        ll a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    dfs(1, 0, 0);

    cout << dp1[1] << '\n';
    return 0;
}

Compilation message (stderr)

beads.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

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