oj.uz

Submission #161836

# Submission time Handle Problem Language Result Execution time Memory
161836 2019-11-04T15:35:12 Z Akashi Chase (CEOI17_chase) C++14
100 / 100
 913 ms 346012 KB 
#include <bits/stdc++.h>
using namespace std;

int n, V;
int val[100005];
bool viz[100005];
long long Sol, sum[100005];
long long down[100005][105][2], up[100005][105][2];
long long up2[100005][105][2], down2[100005][105][2];
long long up3[100005][105][2];

vector <int> v[100005];

void dfs(int nod = 1){
    viz[nod] = 1;

    down[nod][1][1] = max(down[nod][1][1], sum[nod]);
    up[nod][1][1] = max(up[nod][1][1], sum[nod]);

    for(auto fiu : v[nod]){
        if(viz[fiu]) continue ;

        dfs(fiu);

        for(int k = 0; k <= V ; ++k){
            Sol = max(Sol, down[nod][k][0] + up[fiu][V - k][0]);
            Sol = max(Sol, down[nod][k][0] + up[fiu][V - k][1]);
            Sol = max(Sol, down[nod][k][1] + up[fiu][V - k][0] - val[fiu]);
            Sol = max(Sol, down[nod][k][1] + up[fiu][V - k][1] - val[fiu]);

            Sol = max(Sol, down[fiu][k][0] + up[nod][V - k][0]);
            Sol = max(Sol, down[fiu][k][0] + up[nod][V - k][1]);
            Sol = max(Sol, down[fiu][k][1] + up[nod][V - k][0] - val[nod]);
            Sol = max(Sol, down[fiu][k][1] + up[nod][V - k][1] - val[nod]);
        }

        for(int k = 1; k <= V ; ++k){
            down[nod][k][0] = max(max(down[nod][k - 1][0], down[nod][k][0]), max(down[fiu][k][0], down[fiu][k][1] - val[nod]));
            down[nod][k][1] = max(max(down[nod][k - 1][1], down[nod][k][1]), max(down[fiu][k - 1][0], down[fiu][k - 1][1] - val[nod]) + sum[nod]);

            up[nod][k][0] = max(max(up[nod][k][0], up[nod][k - 1][0]), max(up[fiu][k][0], up[fiu][k][1]));
            up[nod][k][1] = max(max(up[nod][k][1], up[nod][k - 1][1]), max(up[fiu][k - 1][0] - val[fiu], up[fiu][k - 1][1] - val[fiu]) + sum[nod]);

            Sol = max(Sol, max(up[nod][k][0], up[nod][k][1]));
            Sol = max(Sol, max(down[nod][k][0], down[nod][k][1]));
        }
    }
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &V);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &val[i]);

    int x, y;
    for(int i = 2; i <= n ; ++i){
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
        v[y].push_back(x);

        sum[x] += val[y];
        sum[y] += val[x];
    }

    dfs();

    printf("%lld", Sol);

    return 0;
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &V);
     ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &val[i]);
         ~~~~~^~~~~~~~~~~~~~~
chase.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2708 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2708 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 11 ms 6080 KB Output is correct
8 Correct 10 ms 6136 KB Output is correct
9 Correct 9 ms 6008 KB Output is correct
10 Correct 10 ms 6008 KB Output is correct
11 Correct 10 ms 6008 KB Output is correct
12 Correct 9 ms 6044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 344596 KB Output is correct
2 Correct 702 ms 344412 KB Output is correct
3 Correct 655 ms 337048 KB Output is correct
4 Correct 521 ms 338156 KB Output is correct
5 Correct 713 ms 338128 KB Output is correct
6 Correct 913 ms 338072 KB Output is correct
7 Correct 718 ms 338112 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2708 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 11 ms 6080 KB Output is correct
8 Correct 10 ms 6136 KB Output is correct
9 Correct 9 ms 6008 KB Output is correct
10 Correct 10 ms 6008 KB Output is correct
11 Correct 10 ms 6008 KB Output is correct
12 Correct 9 ms 6044 KB Output is correct
13 Correct 699 ms 344596 KB Output is correct
14 Correct 702 ms 344412 KB Output is correct
15 Correct 655 ms 337048 KB Output is correct
16 Correct 521 ms 338156 KB Output is correct
17 Correct 713 ms 338128 KB Output is correct
18 Correct 913 ms 338072 KB Output is correct
19 Correct 718 ms 338112 KB Output is correct
20 Correct 711 ms 338164 KB Output is correct
21 Correct 509 ms 338040 KB Output is correct
22 Correct 716 ms 338040 KB Output is correct
23 Correct 519 ms 338168 KB Output is correct
24 Correct 712 ms 338124 KB Output is correct
25 Correct 587 ms 338148 KB Output is correct
26 Correct 688 ms 346012 KB Output is correct
27 Correct 719 ms 345976 KB Output is correct