Submission #756628

#	Time	Username	Problem	Language	Result	Execution time	Memory
756628		Username4132	Beads and wires (APIO14_beads)	C++14	0 / 100	3 ms	4948 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[3][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);
    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};
        cnt++;
    }
    //posiblemente
    sort(d1.begin(), d1.end(), greater<pii>());
    sort(d2.begin(), d2.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];
    }
}

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[2][0]);
}

Compilation message (stderr)

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

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