Submission #30153

#	Time	Username	Problem	Language	Result	Execution time	Memory
30153		Andrei1998	Beads and wires (APIO14_beads)	C++14	28 / 100	1077 ms	5504 KiB

beads

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 200000 + 5;
const int INF = 2E9 + 15;

int N;
vector <pair <int, int> > graph[NMAX];

int dp[NMAX][2];

void dfs(int node, int father) {
    dp[node][0] = 0;
    for (auto it: graph[node])
        if (it.first != father) {
            dfs(it.first, node);
            dp[node][0] += max(dp[it.first][0], dp[it.first][1] + it.second);
        }

    dp[node][1] = -INF;
    for (auto it: graph[node])
        if (it.first != father)
            dp[node][1] = max(dp[node][1], dp[node][0] - max(dp[it.first][0], dp[it.first][1] + it.second) + it.second + dp[it.first][0]);
}

int main()
{
    //freopen("data.in", "r", stdin);

    cin >> N;
    for (int i = 1; i < N; ++ i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    int ans = 0;
    for (int i = 1; i <= N; ++ i) {
        dfs(i, 0);
        ans = max(ans, dp[i][0]);
    }
    cout << ans << '\n';
    return 0;
}

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