Submission #558412

#	Time	Username	Problem	Language	Result	Execution time	Memory
558412		hibiki	Beads and wires (APIO14_beads)	C++11	100 / 100	209 ms	32484 KiB

beads

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second

int n;
long long pw[200005],dp[200005][2][2];
vector<pair<int,long long> > v[200005];

void dfs(int nw,int fa)
{
    if(v[nw].size() == 1 && fa != -1) return ;

    long long sum = 0, b_m = -2e9;

    int c_ty2_m, c_ty2_m2;
    long long v_ty2_m = -2e9, v_ty2_m2 = -2e9;

    int c_ty3_m, c_ty3_m2;
    long long v_ty3_m = -2e9, v_ty3_m2 = -2e9;

    for(pair<int,int> data: v[nw])
    {
        int go = data.F;
        long long edge = data.S;
        if(go == fa) continue;

        pw[go] = edge;

        dfs(go,nw);


        long long base = max(dp[go][0][0], dp[go][1][0]);
        sum += base;

        long long ty1 = max(dp[go][0][1], dp[go][1][1]) - base;
        b_m = max(b_m, ty1);

        long long ty2 = dp[go][0][1] + edge - base;
        if(ty2 > v_ty2_m)
        {
            v_ty2_m2 = v_ty2_m;
            c_ty2_m2 = c_ty2_m;

            v_ty2_m = ty2;
            c_ty2_m = go;
        }
        else if(ty2 > v_ty2_m2)
        {
            v_ty2_m2 = ty2;
            c_ty2_m2 = go;
        }

        long long ty3 = dp[go][0][0] + edge - base;
        if(ty3 > v_ty3_m)
        {
            v_ty3_m2 = v_ty3_m;
            c_ty3_m2 = c_ty3_m;

            v_ty3_m = ty3;
            c_ty3_m = go;
        }
        else if(ty3 > v_ty3_m2)
        {
            v_ty3_m2 = ty3;
            c_ty3_m2 = go;
        }
    }

    dp[nw][0][0] = sum;
    dp[nw][0][1] = sum + max(0ll, b_m);

    if(c_ty2_m != c_ty3_m)
        dp[nw][0][1] = max(dp[nw][0][1], sum + v_ty2_m + v_ty3_m);
    else
    {
        dp[nw][0][1] = max(dp[nw][0][1], sum + v_ty2_m + v_ty3_m2);
        dp[nw][0][1] = max(dp[nw][0][1], sum + v_ty2_m2 + v_ty3_m);
    }

    dp[nw][1][0] = sum + pw[nw] + v_ty3_m;
    dp[nw][1][1] = sum + pw[nw] + v_ty2_m;
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n - 1; i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        v[a].pb({b,c});
        v[b].pb({a,c});
    }

    dfs(1, -1);

    printf("%lld\n",max(dp[1][0][0],dp[1][0][1]));

    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18:18: warning: variable 'c_ty2_m2' set but not used [-Wunused-but-set-variable]
   18 |     int c_ty2_m, c_ty2_m2;
      |                  ^~~~~~~~
beads.cpp:21:18: warning: variable 'c_ty3_m2' set but not used [-Wunused-but-set-variable]
   21 |     int c_ty3_m, c_ty3_m2;
      |                  ^~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
beads.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:75:5: warning: 'c_ty3_m' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     if(c_ty2_m != c_ty3_m)
      |     ^~
beads.cpp:75:5: warning: 'c_ty2_m' may be used uninitialized in this function [-Wmaybe-uninitialized]

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