oj.uz

Submission #483390

# Submission time Handle Problem Language Result Execution time Memory
483390 2021-10-29T04:07:33 Z blue Beads and wires (APIO14_beads) C++17
0 / 100
 5 ms 9676 KB 
#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, dp[v][1][0] - 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -