Submission #758825

#	Time	Username	Problem	Language	Result	Execution time	Memory
758825		Username4132	Beads and wires (APIO14_beads)	C++14	100 / 100	159 ms	33432 KiB

beads

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=200010, INF=2000000010;
int n, dp[4][MAXN];
vector<pii> g[MAXN];

void dfs(int v, int p, int cost){
    int sz = g[v].size() - (v!=0), cnt=0;
    vector<pii> d1(sz), d2(sz), d3(sz);
    for(pii to:g[v]) if(to.F!=p){
        dfs(to.F, v, to.S);
        dp[1][v]+=dp[0][to.F];
        d1[cnt]={to.S+dp[1][to.F]-dp[0][to.F], cnt};
        d2[cnt]={to.S+dp[2][to.F]-dp[0][to.F], cnt};
        d3[cnt]={dp[3][to.F]-dp[0][to.F], cnt};
        cnt++;
    }
    sort(d1.begin(), d1.end(), greater<pii>());
    sort(d2.begin(), d2.end(), greater<pii>());
    sort(d3.begin(), d3.end(), greater<pii>());

    dp[0][v]=(sz==0? 0 : max(d1[0].F + cost, 0))+dp[1][v];
    dp[2][v]=dp[1][v];
    if(sz>1){
        int mx;
        if(d1[0].S!=d2[0].S) mx=d1[0].F+d2[0].F;
        else mx=max(d1[0].F+d2[1].F, d1[1].F+d2[0].F);
        if(mx>0) dp[2][v]=mx+dp[1][v];
    }
    if(sz>0) dp[2][v]=max(dp[2][v], dp[1][v]+d3[0].F);
    if(sz>0) dp[3][v]=max(dp[3][v], dp[1][v]+d2[0].F+cost);
    dp[3][v]=max(dp[3][v], dp[2][v]);
    dp[3][v]=max(dp[3][v], dp[0][v]);
}

int main(){
    scanf("%d", &n);
    forn(i, n-1){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c); --a, --b;
        g[a].PB({b, c}), g[b].PB({a, c});
    }
    dfs(0, 0, -INF);
    printf("%d\n", dp[3][0]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d %d %d", &a, &b, &c); --a, --b;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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