Submission #1066570

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

beads

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second
vector<pii> to[200010];
int dp[200010][2], un[200010][2]; //0 no unfinished, 1 one unfinished, dp root, un root+edge
void dfs(int x, int pre)
{
    for (auto it: to[x])
    {
        int y = it.f, w = it.s;
        if (y == pre)
            continue;
        dfs(y, x);
        un[y][0] = dp[y][1]+w, un[y][1] = dp[y][0]+w;
        if (dp[y][1] == -1)
            un[y][0] = 0;
    }
    if (to[x].size()-min(1, pre) == 0) //leaf node
    {
        dp[x][1] = -1;
        return;
    }
    else if (to[x].size()-min(1, pre) == 1) //only one child
    {
        int y = to[x][0].f;
        if (y == pre)
            y = to[x][1].f;
        dp[x][0] = un[y][0], dp[x][1] = un[y][1];
        return;
    }
    else if (to[x].size()-min(1, pre) == 2)
    {
        int tdp = 0, mx = 0;
        for (auto it: to[x])
            if (it.first != pre)
            {
                dp[x][0] += un[it.f][0];
                tdp += un[it.f][1];
                mx = max(mx, un[it.f][1]-un[it.f][0]);
            }
        dp[x][1] = dp[x][0]+mx;
        dp[x][0] = max(dp[x][0], tdp);
        return;
    }
    // calculate dp[x][0]
    // connect two children
    int mx1 = -1e9, mx2 = -1e9, mx3 = -1e9;
    for (auto it: to[x])
        if (it.first != pre)
        {
            dp[x][0] += un[it.f][0];
            int x = un[it.f][1]-un[it.f][0];
            if (x >= mx1)
                mx3 = mx2, mx2 = mx1, mx1 = x;
            else if (x >= mx2)
                mx3 = mx2, mx2 = x;
            else if (x >= mx3)
                mx3 = x;
        }
    int tdp = dp[x][0]+mx1+mx2;
    // calculate dp[x][1]
    dp[x][1] = dp[x][0]+mx1;
    dp[x][0] = max(dp[x][0], tdp);
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, i;
    cin >> n;
    for (i = 0; i < n-1; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        to[a].push_back({b, c});
        to[b].push_back({a, c});
    }
    memset(dp, 0, sizeof(dp));
    memset(un, 0, sizeof(un));
    dfs(1, 0);
    //for (i =1 ; i <= n; i++)
        //cout << dp[i][0] << ' ' << dp[i][1] << '\n';
    if (to[1].size() > 1)
        cout << dp[1][0] << '\n';
    else if (to[1].size() == 1)
        cout << max(dp[1][0], dp[to[1][0].f][0]);
    else
        cout << 0 << '\n';
    return 0;
}

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