Submission #457554

#	Time	Username	Problem	Language	Result	Execution time	Memory
457554		prvocislo	Beads and wires (APIO14_beads)	C++17	0 / 100	18 ms	15948 KiB

beads

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 2e5 + 5;
const int inf = 2e9 + 5;
vector<vector<int> > dp(maxn, vector<int>(2, -inf));
vector<vector<pair<int, int> > > g(maxn);
void upd(int& a, const int& b)
{
    a = max(a, b);
}
void dfs(int u, int p, int w)
{
    vector<int> dp2(3, -inf);
    dp2[0] = 0;
    for (const pair<int, int>& v : g[u])
    {
        if (v.first == p)
        {
            continue;
        }
        dfs(v.first, u, v.second);
        vector<int> dpnw(3, -inf);
        for (int i = 0; i < 3; i++)
        {
            upd(dpnw[i], dp2[i] + max(dp[v.first][0], dp[v.first][1]));
            if (i != 2)
            {
                upd(dpnw[i + 1], dp2[i] + dp[v.first][0] + v.second);
            }
        }
        dp2 = dpnw;
    }
    upd(dp[u][0], dp2[0]);
    upd(dp[u][0], dp2[2]);
    if (p != -1)
    {
        upd(dp[u][1], dp2[1] + w);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[--a].push_back({ --b, c });
        g[b].push_back({ a, c });
    }
    dfs(0, -1, -1);
    cout << dp[0][0] << "\n";
    return 0;
}

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