Submission #158434

#	Time	Username	Problem	Language	Result	Execution time	Memory
158434		mhy908	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define inf 1987654321
using namespace std;
typedef long long LL;
int n;
LL dp1[200010], dp2[200010], dp3[200010], dp[200010];
vector<pair<int, LL> > link[200010];
void get_dp(int num, int par, LL c)
{
    LL sum=0;
    vector<LL> comp;
    for(int i=0; i<link[num].size(); i++){
        if(par==link[num][i].F)continue;
        get_dp(link[num][i].F, num, link[num][i].S);
        sum+=dp[link[num][i].F];
        comp.pb(-dp[link[num][i].F]+max(dp3[link[num][i].F], dp2[link[num][i].F])+link[num][i].S);
        dp3[num]=max(dp3[num], dp[link[num][i].F]);
    }
    sort(comp.begin(), comp.end(), greater<LL>());
    if(comp.size()>=1)dp1[num]=sum+comp[0]+c;
    if(comp.size()>=2)dp2[num]=sum+comp[0]+comp[1];
    dp[num]=max(dp3[num], max(dp1[num], dp2[num]));
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        link[a].pb(mp(b, c));
        link[b].pb(mp(a, c));
    }
    get_dp(1, 0, -inf);
    printf("%lld", dp[1]);
}

Compilation message (stderr)

beads.cpp: In function 'void get_dp(int, int, LL)':
beads.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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