Submission #198231

#	Time	Username	Problem	Language	Result	Execution time	Memory
198231		parsa_mobed	Beads and wires (APIO14_beads)	C++14	28 / 100	1056 ms	3064 KiB

beads

#include <bits/stdc++.h>

using namespace std;
#define pii pair <int , int>
#define F first
#define S second
const int N = 1e5 + 10, inf = 1e9 + 5;
int dp[N][2];
vector <pii> g[N];

void dfs(int v, int p = 0)
{
    int sum = 0;
    for (pii u : g[v]) if (u.F != p) {
        dfs(u.F, v);
        sum += max(dp[u.F][1] + u.S, dp[u.F][0]);
    }
    dp[v][0] = sum;
    for (pii u : g[v]) if (u.F != p)
        dp[v][1] = max(dp[v][1], sum - max(dp[u.F][1] + u.S, dp[u.F][0]) + dp[u.F][0] + u.S);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = -inf;
        dfs(i);
        ans = max(ans, dp[i][0]);
    }
    cout << ans << "\n";
}

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