Submission #36804

#	Time	Username	Problem	Language	Result	Execution time	Memory
36804		imaxblue	Beads and wires (APIO14_beads)	C++14	100 / 100	212 ms	24308 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009

ll dp[200005][5];
int n, a, b, d;
//Case 0: new branch/nothing
//Case 1: Going upwards
//Case 2: new branch, root below
//Case 3: Going upwards, root below
vector<pii> v[200005];
void dfs(int N, int P, int D){
    dp[N][2]=dp[N][3]=-(1 << 30);
    ll nxt=-(1 << 30); int o, o2;
    dp[N][0]=-(1 << 30);
    for (int l=0; l<v[N].size(); ++l){
        if (v[N][l].x==P) continue;
        dfs(v[N][l].x, N, v[N][l].y);

        dp[N][2]=max(dp[N][2], dp[N][0]+dp[v[N][l].x][2]-dp[v[N][l].x][0]);
        dp[N][2]=max(dp[N][2], dp[N][3]+dp[v[N][l].x][1]-dp[v[N][l].x][0]);

        if (dp[v[N][l].x][1]-dp[v[N][l].x][0]+D>dp[N][0]){
            nxt=dp[N][0];
            dp[N][0]=dp[v[N][l].x][1]-dp[v[N][l].x][0]+D;
        } else nxt=max(nxt, dp[v[N][l].x][1]-dp[v[N][l].x][0]+D);
        dp[N][1]+=dp[v[N][l].x][0];
        dp[N][2]=max(dp[N][2], dp[v[N][l].x][3]-dp[v[N][l].x][0]+D);
        dp[N][2]=max(dp[N][2], dp[v[N][l].x][2]-dp[v[N][l].x][0]-v[N][l].y+D);
        dp[N][3]=max(dp[N][3], dp[v[N][l].x][2]-dp[v[N][l].x][0]+D);
    }
    dp[N][2]=max(dp[N][2], dp[N][0]+nxt-D);
    dp[N][2]+=dp[N][1];
    dp[N][0]=max(0LL, dp[N][0]);
    dp[N][0]+=dp[N][1];
    dp[N][3]+=dp[N][1];
    dp[N][1]+=D;
    /*cout << N << ": ";
    for (int l=0; l<4; ++l){
        cout << dp[N][l] << ' ';
    }
    cout << endl;*/
}
int main(){
    scanf("%i", &n);
    for (int l=0; l<n-1; ++l){
        scanf("%i%i%i", &a, &b, &d);
        v[a].pb(mp(b, d));
        v[b].pb(mp(a, d));
    }
    dfs(1, -1, 0);
    cout << max(dp[1][1], dp[1][2]);
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<v[N].size(); ++l){
                   ~^~~~~~~~~~~~
beads.cpp:28:28: warning: unused variable 'o' [-Wunused-variable]
     ll nxt=-(1 << 30); int o, o2;
                            ^
beads.cpp:28:31: warning: unused variable 'o2' [-Wunused-variable]
     ll nxt=-(1 << 30); int o, o2;
                               ^~
beads.cpp: In function 'int main()':
beads.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i", &a, &b, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43