oj.uz

Submission #699096

# Submission time Handle Problem Language Result Execution time Memory
699096 2023-02-15T15:17:26 Z Ronin13 Beads and wires (APIO14_beads) C++14
0 / 100
 8 ms 12068 KB 
#include <bits/stdc++.h>
#define ll long  long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =500001;

/*

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
ll dp[nmax][2][2];
ll val[nmax];

vector <vector <pii> > g(nmax);

void dfs(int v, int e = -1){
    ll mx = -1e9;
    pair<pll, pll> mx1;
    pair<pll, pll> mx2;
    pair<pll, pll> mx3, mx4;
    mx1 = mx2 = mx3 = mx4 = {{mx, mx}, {mx, mx}};
    ll MX = -1e9;
    for(auto ed : g[v]){
        int to = ed.f;
        ll len = ed.s;
        if(to == e) continue;
        val[to] = len;
        dfs(to, v);
        ll y = max(dp[to][1][0], dp[to][0][0]);
        dp[v][0][0] += y;
        mx = max(mx, dp[to][0][0] - y + val[to]);
        ll z = dp[to][0][1] - y + val[to];
        mx1.s = max(mx1.s, {z, to});
        if(mx1.f < mx1.s)
            swap(mx1.f, mx1.s);
        z = dp[to][0][0] - y + val[to];
        mx2.s = max(mx2.s, {z, to});
        if(mx2.f < mx2.s)
            swap(mx2.f, mx2.s);
        MX = max(MX, dp[to][0][1] - y + val[to]);
        z = max(dp[to][1][1], dp[to][0][1]) - y;
        mx3.s = max(mx3.s, {z, to});
        if(mx3.f < mx3.s)
            swap(mx3.f, mx3.s);
        z = dp[to][0][0] - y + val[to];
        mx4.s = max(mx4.s, {z, to});
        if(mx4.f < mx4.s)
            swap(mx4.f, mx4.s);
    }
    dp[v][1][0] = max(dp[v][1][0], mx + dp[v][0][0] + val[v]);
    if(mx1.f.s == mx2.f.s){
        dp[v][0][1] = dp[v][0][0] + max(mx1.f.f + mx2.s.f, mx1.s.f + mx2.f.f);
    }
    else dp[v][0][1] = max(dp[v][0][1], dp[v][0][0] + mx1.f.f + mx2.f.f);
    dp[v][1][1] = dp[v][0][0] + MX;
    if(mx3.f.f == mx4.f.f){
        dp[v][1][1] = max(dp[v][1][1], dp[v][0][0] + mx3.f.f + mx4.s.f);
        dp[v][1][1] = max(dp[v][1][1], dp[v][0][0] + mx4.f.f + mx3.s.f);
    }
    else
        dp[v][1][1] = max(dp[v][1][1], dp[v][0][0] + mx4.f.f + mx3.f.f);
    dp[v][0][1] = max(dp[v][0][1], dp[v][0][0]);
    dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]);
}

int32_t main() {
    int n; cin >> n;
    val[1] = -1e9;
    for(int i = 1; i < n; i++){
        int u, v, c; cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    dfs(1);
    cout << max(dp[1][0][1], dp[1][0][0]);
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Incorrect 8 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Incorrect 8 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Incorrect 8 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Incorrect 8 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -