oj.uz

Submission #483400

# Submission time Handle Problem Language Result Execution time Memory
483400 2021-10-29T07:01:54 Z blue Beads and wires (APIO14_beads) C++17
100 / 100
 389 ms 48944 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, 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.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 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9692 KB Output is correct
7 Correct 6 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 7 ms 9776 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct

Subtask #2
15.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 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9692 KB Output is correct
7 Correct 6 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 7 ms 9776 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 5 ms 9712 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9676 KB Output is correct
16 Correct 5 ms 9676 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 5 ms 9772 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 6 ms 9676 KB Output is correct
22 Correct 5 ms 9676 KB Output is correct

Subtask #3
29.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 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9692 KB Output is correct
7 Correct 6 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 7 ms 9776 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 5 ms 9712 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9676 KB Output is correct
16 Correct 5 ms 9676 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 5 ms 9772 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 6 ms 9676 KB Output is correct
22 Correct 5 ms 9676 KB Output is correct
23 Correct 9 ms 10296 KB Output is correct
24 Correct 10 ms 10188 KB Output is correct
25 Correct 8 ms 10296 KB Output is correct
26 Correct 12 ms 10808 KB Output is correct
27 Correct 11 ms 10816 KB Output is correct
28 Correct 14 ms 11392 KB Output is correct
29 Correct 13 ms 11260 KB Output is correct
30 Correct 12 ms 11212 KB Output is correct
31 Correct 13 ms 12108 KB Output is correct

Subtask #4
43.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 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9692 KB Output is correct
7 Correct 6 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 7 ms 9776 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 5 ms 9712 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9676 KB Output is correct
16 Correct 5 ms 9676 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 5 ms 9772 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 6 ms 9676 KB Output is correct
22 Correct 5 ms 9676 KB Output is correct
23 Correct 9 ms 10296 KB Output is correct
24 Correct 10 ms 10188 KB Output is correct
25 Correct 8 ms 10296 KB Output is correct
26 Correct 12 ms 10808 KB Output is correct
27 Correct 11 ms 10816 KB Output is correct
28 Correct 14 ms 11392 KB Output is correct
29 Correct 13 ms 11260 KB Output is correct
30 Correct 12 ms 11212 KB Output is correct
31 Correct 13 ms 12108 KB Output is correct
32 Correct 57 ms 15452 KB Output is correct
33 Correct 43 ms 15488 KB Output is correct
34 Correct 42 ms 15428 KB Output is correct
35 Correct 266 ms 33432 KB Output is correct
36 Correct 282 ms 33360 KB Output is correct
37 Correct 267 ms 33444 KB Output is correct
38 Correct 337 ms 44224 KB Output is correct
39 Correct 389 ms 42868 KB Output is correct
40 Correct 371 ms 41688 KB Output is correct
41 Correct 305 ms 48944 KB Output is correct