Submission #457811

#	Time	Username	Problem	Language	Result	Execution time	Memory
457811		prvocislo	Beads and wires (APIO14_beads)	C++17	0 / 100	39 ms	34728 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<vector<ll> > > dp(maxn, vector<vector<ll> >(2, vector<ll>(2, -inf)));
vector<vector<pair<int, int> > > g(maxn);
void upd(ll& a, const ll& b) { a = max(a, b); }
void dfs(int u, int p, int w)
{
    vector<vector<ll> > dp2(3, vector<ll>(2, -inf)); // pocet hran ktore idu nadol, mam uz zly podstrom?
    dp2[0][0] = 0;
    for (const pair<int, int>& v : g[u])
    {
        if (v.first == p) continue;
        dfs(v.first, u, v.second);
        vector<vector<ll> > dpnw(3, vector<ll>(2, -inf));
        for (int i = 0; i < 3; i++)
        {
            // nepride zly podstrom
            for (int j = 0; j < 2; j++)
            {
                upd(dpnw[i][j], dp2[i][j] + max(dp[v.first][0][0], dp[v.first][1][0])); // nepridam novu hranu, ani zly vrchol
                if (i < 2 && (j == 0 || i > 0)) // nemozem pridat novu hranu ak sme uz mali zly podstrom ktory nie je napojeny
                    upd(dpnw[i + 1][j], dp2[i][j] + dp[v.first][0][0] + v.second); // pridam novu hranu
            }
            // pride novy zly podstrom
            if (i < 2) upd(dpnw[i + 1][1], dp2[i][0] + dp[v.first][0][1] + v.second);
        }
        upd(dpnw[0][1], dp2[0][0] + dp[v.first][0][1]);
        dp2 = dpnw;
    }
    upd(dp[u][0][0], dp2[0][0]); // nie som stred, nemam zly vrchol
    upd(dp[u][0][1], dp2[0][1]); // nie som stred, mam zly vrchol
    upd(dp[u][0][1], dp2[2][0]); // som stred, dve hrany nadol, nemam zly vrchol
    upd(dp[u][0][1], dp2[2][1]); // som stred, dve hrany nadol, mam zly vrchol
    if (p > -1) upd(dp[u][1][0], dp2[1][0] + w); // som stred, jedna hrana nadol, nemam zly vrchol
    if (p > -1) upd(dp[u][1][1], dp2[1][1] + w); // som stred, jedna hrana nadol, mam zly vrchol
}
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 << max(dp[0][0][0], dp[0][0][1]) << "\n";
    return 0;
}

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