oj.uz

Submission #116604

# Submission time Handle Problem Language Result Execution time Memory
116604 2019-06-13T04:54:56 Z jangwonyoung Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5120 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N=2e5+1;
int n;
int dp[N][4];
int p[N],pl[N];
int z[4];
vector<pair<int,int> >adj[N];
void dfs(int id){
    for(auto cur:adj[id]){
        if(cur.se==p[id]) continue;
        p[cur.se]=id,pl[cur.se]=cur.fi;
        dfs(cur.se);
    }
}
void solve(int id){
    z[0]=z[1]=z[2]=z[3]=-2e9;z[1]=0;
    for(auto cur:adj[id]){//doesnt take node i as merger
        if(cur.se==p[id]) continue;
        solve(cur.se);
        z[3]=max(z[3]+max(dp[cur.se][0],dp[cur.se][1]),z[1]+max(dp[cur.se][2],dp[cur.se][3]));
        z[1]=z[1]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][1]=max(dp[id][1],z[1]);dp[id][3]=max(dp[id][3],z[3]);
    z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
    for(auto cur:adj[id]){//merge horizontally
        if(cur.se==p[id]) continue;
        z[3]=z[3]+max(dp[cur.se][0],dp[cur.se][1]);
        z[3]=max(z[3],max(z[2]+dp[cur.se][1],z[1]+max(dp[cur.se][1],dp[cur.se][3]))+pl[cur.se]);
        z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+max(dp[cur.se][1],dp[cur.se][3])+pl[cur.se]);
        z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
        z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][3]=max(dp[id][3],z[3]);
    if(id==1) return;
    z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
    for(auto cur:adj[id]){//merge vertically
        if(cur.se==p[id]) continue;
        z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+max(dp[cur.se][3],dp[cur.se][1])+pl[cur.se]);
        z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
        z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][2]=max(dp[id][2],z[2]+pl[id]);dp[id][0]=max(dp[id][0],z[1]+pl[id]);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<n ;i++){
        int u,v,w;cin >> u >> v >> w;
        adj[u].pb({w,v});adj[v].pb({w,u});
    }
    dfs(1);
    solve(1);
    cout << max(max(dp[1][0],dp[1][1]),max(dp[1][2],dp[1][3])) << '\n';
}

Subtask #1
0 / 13.0

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