oj.uz

Submission #699007

# Submission time Handle Problem Language Result Execution time Memory
699007 2023-02-15T09:34:08 Z Ronin13 Beads and wires (APIO14_beads) C++14
0 / 100
 7 ms 12064 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;

int dp[nmax][3];
int val[nmax];

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

void dfs(int v, int e = -1){
    pair <pii, pii> mx1, mx2;
    mx1 = {{-1e9, -1e9}, {-1e9, -1e9}};
    mx2 = mx1;
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        int x = ed.s;
        val[to] = x;
        dfs(to, v);
        dp[v][0] += max({dp[to][0], dp[to][1], dp[to][2]});
        int vv = max(dp[to][0], dp[to][2]) - max({dp[to][0], dp[to][1], dp[to][2]}) + val[to];
        int uu = dp[to][0] - max({dp[to][0], dp[to][1], dp[to][2]}) + val[to];
        mx1.s = max(mx1.s, {vv, to});
        mx2.s = max(mx2.s, {uu, to});
        if(mx1.s.f > mx1.f.f)
            swap(mx1.s, mx1.f);
        if(mx2.s.f > mx2.f.f)
            swap(mx2.s, mx2.f);
    }
    dp[v][1] = dp[v][0] + mx1.f.f + val[v];
    if(mx1.f.s == mx2.f.s){
        dp[v][2] = dp[v][0] + mx1.f.f + mx2.s.f;
        dp[v][2] = max(dp[v][2], dp[v][0] + mx1.s.f + mx2.f.f);
    }
    else dp[v][2] = dp[v][0] + mx1.f.f + mx2.f.f;
}

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], dp[1][2]);
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Incorrect 6 ms 12064 KB Output isn't correct
8 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 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Incorrect 6 ms 12064 KB Output isn't correct
8 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 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Incorrect 6 ms 12064 KB Output isn't correct
8 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 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Incorrect 6 ms 12064 KB Output isn't correct
8 Halted 0 ms 0 KB -