oj.uz

Submission #538829

# Submission time Handle Problem Language Result Execution time Memory
538829 2022-03-17T20:54:27 Z Lobo Beads and wires (APIO14_beads) C++17
0 / 100
 3 ms 4948 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 200020

int n, dp[maxn][2], ans;
pair<int,int> mxv[maxn];
vector<pair<int,int>> g[maxn];

// dp(u,1) ta com azul pro pai e vai ter qual o melhor pra continuar assim
// 

void dfs(int u, int p) {
    int ans1 = 0;
    mxv[u] = mp(-inf,-inf);

    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == p) continue;

        dfs(v,u);
        ans1+= max(dp[v][0],dp[v][1]+w);
        mxv[u].sc = max(mxv[u].sc, dp[v][0] + w - max(dp[v][0],dp[v][1]+w));
        if(mxv[u].sc > mxv[u].fr) swap(mxv[u].fr,mxv[u].sc);
    }



    dp[u][0] = ans1;
    dp[u][1] = ans1+mxv[u].fr;

    // cout << u << " -- " << dp[u][0] << " " << dp[u][1] << endl;
}

void reroot(int u, int p, int wp) {
    //p é a raiz da tree até entao
    //tiro o u do p e insiro o p no u
    int antu0 = dp[u][0];
    int antu1 = dp[u][1];
    int antp0 = dp[p][0];
    int antp1 = dp[p][1];

    //tirar u do p
    dp[p][0]-= max(dp[u][0],dp[u][1]+wp);
    if(mxv[p].fr == dp[u][0] + wp - max(dp[u][0],dp[u][1]+wp)) dp[p][1] = dp[p][0]+mxv[p].sc;
    else dp[p][1] = dp[p][0] + mxv[p].fr;

    //insiro p em u
    dp[u][0]+= max(dp[p][0],dp[p][1]+wp);
    dp[u][1] = dp[u][0] + max(mxv[u].fr,dp[p][0] + wp - max(dp[p][0],dp[p][1]+wp));

    ans = max(ans, dp[u][0]);

    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == p) continue;

        reroot(v,u,w);
    }

    //volta as respostas anteriores
    dp[u][0] = antu0;
    dp[u][1] = antu1;
    dp[p][0] = antp0;
    dp[p][1] = antp1;

}

void solve() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u,v,w; cin >> u >> v >> w;

        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }

    dfs(1,1);
    ans = dp[1][0];
    for(auto V : g[1]) {
        int v = V.fr;
        int w = V.sc;
        reroot(v,1,w);
    }

    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Subtask #1
0 / 13.0

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