oj.uz

Submission #240885

# Submission time Handle Problem Language Result Execution time Memory
240885 2020-06-21T11:43:18 Z nvmdava Beads and wires (APIO14_beads) C++17
0 / 100
 7 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;

vector<pair<int, int> > adj[N];

ll ans = 0;

ll dp[N][2][2];

void dfs1(int v, int p = 0, int d = 0){
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dfs1(x.ff, v, x.ss);
    }
    ll mx = 0;
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dp[v][0][0] += dp[x.ff][0][1];
        mx = max(mx, d + dp[x.ff][0][0] + x.ss - dp[x.ff][0][1]);
    }
    if(p == 0) mx = 0;
    dp[v][0][1] = dp[v][0][0] + mx;
    ans = max(ans, dp[v][0][1]);
}

void dfs2(int v, int p = 0, ll d = 0){
    ll t = dp[v][1][1];

    ll mx1 = (p == 0 ? -99999999999 : d + dp[v][1][0] - dp[v][1][1]), mx2 = -9999999999999;
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        t += dp[x.ff][0][1];
        ll w = x.ss + dp[x.ff][0][0] - dp[x.ff][0][1];
        if(w > mx1){
            mx2 = mx1;
            mx1 = w;
        } else mx2 = max(mx2, w);
    }

    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dp[x.ff][1][0] = t - dp[x.ff][0][1];
        ll w = x.ss + dp[x.ff][0][0] - dp[x.ff][0][1];
        dp[x.ff][1][1] = dp[x.ff][1][0] + max(0LL, x.ss + (w == mx1 ? mx2 : mx1));
        ans = max(ans, dp[x.ff][1][1]);
        dfs2(x.ff, v, x.ss);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    for(int x, y, z, i = 1; i < n; ++i){
        cin>>x>>y>>z;
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }
    dfs1(1);
    dfs1(2);

    cout<<ans;

}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -