Submission #483400

#	Time	Username	Problem	Language	Result	Execution time	Memory
483400		blue	Beads and wires (APIO14_beads)	C++17	100 / 100	389 ms	48944 KiB

beads

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

const long long INF = 2'000'000'001;

const int maxN = 200'000;
int N;
vector<int> edge[1+maxN];
vector<long long> wt[1+maxN];

long long dp[1+maxN][2][2];

void dfs(int u, int p)
{
    // cerr << "dfs " << u << ' ' << p << '\n';
    int ct = 0;

    long long compl_sum = 0;
    long long adj_01 = -INF;
    long long adj_11 = -INF;

    multiset<long long> adj_set;
    vector<long long> adj_vec;

    long long simpl_adj = -INF;

    for(int e = 0; e < int(edge[u].size()); e++)
    {
        int v = edge[u][e];
        long long w = wt[u][e];

        if(v == p) continue;

        dfs(v, u);


        ct++;

        long long compl_v = max(dp[v][0][0], dp[v][0][1] + w);

        compl_sum += compl_v;
        adj_01 = max(adj_01, dp[v][0][0] + w - compl_v);
        adj_11 = max(adj_11, w + dp[v][1][0] - compl_v);

        adj_set.insert(w + dp[v][1][0] - compl_v);
        adj_vec.push_back(w + dp[v][0][0] - compl_v);

        simpl_adj = max(simpl_adj, max(dp[v][1][0], dp[v][1][1] + w) - compl_v);
    }



    if(ct == 0)
    {
        dp[u][0][0] = 0;
        dp[u][1][0] = -INF;
        dp[u][0][1] = -INF;
        dp[u][1][1] = -INF;

        // cerr << u << ": " << dp[u][0][0] << ' ' << dp[u][0][1] << ' ' << dp[u][1][0] << ' ' << dp[u][1][1] << '\n';

        return;
    }



    dp[u][0][0] = compl_sum;

    dp[u][0][1] = compl_sum + adj_01;

    dp[u][1][1] = compl_sum + adj_11;


    dp[u][1][0] = -INF;

    dp[u][1][0] = max(dp[u][1][0], compl_sum + simpl_adj);
    sort(adj_vec.begin(), adj_vec.end());


    if(ct >= 2)
    {
        if(ct >= 2)
            dp[u][1][0] = max(dp[u][1][0], compl_sum + adj_vec[int(adj_vec.size()) - 1] + adj_vec[int(adj_vec.size()) - 2]);

        for(int e = 0; e < int(edge[u].size()); e++)
        {
            int v = edge[u][e];
            if(v == p) continue;
            long long w = wt[u][e];

            long long compl_v = max(dp[v][0][0], dp[v][0][1] + w);

            adj_set.erase(adj_set.find(w + dp[v][1][0] - compl_v));
            dp[u][1][0] = max(dp[u][1][0], compl_sum + *adj_set.rbegin() +   w + dp[v][0][0] - compl_v);
            adj_set.insert(w + dp[v][1][0] - compl_v);
        }
    }



    // cerr << u << ": " << dp[u][0][0] << ' ' << dp[u][0][1] << ' ' << dp[u][1][0] << ' ' << dp[u][1][1] << '\n';


}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int e = 1; e <= N-1; e++)
    {
        int u, v;
        long long w;
        cin >> u >> v >> w;

        edge[u].push_back(v);
        wt[u].push_back(w);

        edge[v].push_back(u);
        wt[v].push_back(w);
    }

    dfs(1, 0);

    long long ans = max(dp[1][0][0], dp[1][1][0]);

    cout << ans << '\n';
}

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