oj.uz

Submission #491227

# Submission time Handle Problem Language Result Execution time Memory
491227 2021-12-01T03:08:33 Z Saacoota Beads and wires (APIO14_beads) C++14
0 / 100
 3 ms 4940 KB 
#include <bits/stdc++.h>
#define ii pair < int , int >
#define fi first
#define se second

using namespace std;

const int maxn = 200010;
const int inf = 0x3f3f3f3f;

vector < ii > g[maxn];
int dp[maxn][3] , f[maxn];

void DFS(int u,int p,int wp) {
    for (auto v : g[u])
    if (v.fi != p)
        DFS(v.fi , u , v.se);
    for (auto v : g[u])
    if (v.fi != p)
        dp[u][0] += max(dp[v.fi][0] , dp[v.fi][1]);
    for (auto v : g[u])
    if (v.fi != p)
        dp[u][1] = max(dp[u][1] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][0] + wp + v.se);
    dp[u][2] = dp[u][0];
    int ma1 , ma2;
    ma1 = ma2 = -inf;
    for (auto v : g[u])
    if (v.fi != p) {
        int cur = dp[v.fi][2] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se;
        if (cur > ma1) {
            ma2 = ma1;
            ma1 = cur;
        } else ma2 = max(ma2 , cur);
    }
    for (auto v : g[u])
    if (v.fi != p) {
        int cur = ma1;
        if (cur == dp[v.fi][0] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se) cur = ma2;
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2]);
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2] + cur + v.se);
        dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + f[v.fi] + v.se);
    }
    f[u] = -inf;
    for (auto v : g[u])
    if (v.fi != p)
        f[u] = max(f[u] , dp[v.fi][2] + v.se + dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1 ; i < n ; ++i) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].emplace_back(v , w);
        g[v].emplace_back(u , w);
    }
    DFS(1 , 0 , 0);
    cout << dp[1][2];
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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