oj.uz

Submission #558412

# Submission time Handle Problem Language Result Execution time Memory
558412 2022-05-07T09:21:09 Z hibiki Beads and wires (APIO14_beads) C++11
100 / 100
 209 ms 32484 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4988 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4960 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5008 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5012 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4988 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4960 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5008 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5012 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 5 ms 5508 KB Output is correct
25 Correct 6 ms 5460 KB Output is correct
26 Correct 8 ms 6048 KB Output is correct
27 Correct 10 ms 6168 KB Output is correct
28 Correct 11 ms 6048 KB Output is correct
29 Correct 7 ms 5716 KB Output is correct
30 Correct 7 ms 6020 KB Output is correct
31 Correct 7 ms 6572 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4988 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4960 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5008 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5012 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 5 ms 5508 KB Output is correct
25 Correct 6 ms 5460 KB Output is correct
26 Correct 8 ms 6048 KB Output is correct
27 Correct 10 ms 6168 KB Output is correct
28 Correct 11 ms 6048 KB Output is correct
29 Correct 7 ms 5716 KB Output is correct
30 Correct 7 ms 6020 KB Output is correct
31 Correct 7 ms 6572 KB Output is correct
32 Correct 29 ms 10316 KB Output is correct
33 Correct 35 ms 10264 KB Output is correct
34 Correct 32 ms 10188 KB Output is correct
35 Correct 209 ms 26532 KB Output is correct
36 Correct 162 ms 26500 KB Output is correct
37 Correct 170 ms 26564 KB Output is correct
38 Correct 134 ms 25848 KB Output is correct
39 Correct 110 ms 19496 KB Output is correct
40 Correct 113 ms 25720 KB Output is correct
41 Correct 147 ms 32484 KB Output is correct