oj.uz

Submission #409289

# Submission time Handle Problem Language Result Execution time Memory
409289 2021-05-20T14:01:14 Z Hazem Chase (CEOI17_chase) C++14
100 / 100
 667 ms 488160 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 1e5+10;
const int M = 101;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 4294967296;
const double PI = 3.141592653589793;

LL dp[N][M];
int a[N];
int mxnode[N][M][2];
pair<LL,LL>mx[N][M][2];

vector<int>adj[N];
int n,k;

void dfs(int i,int pre){

    LL sum = 0;
    for(auto x:adj[i])
        if(x!=pre)
            dfs(x,i),sum += 0ll+a[x];

    for(auto x:adj[i]){
        if(x==pre)continue;
        for(int j=1;j<=100;j++)
            dp[i][j] = max(dp[i][j],max(dp[x][j],dp[x][j-1]+sum));
    }
}

LL ans = 0;
void rootshift(int i,int pre){

    LL sum = 0;
    for(auto x:adj[i])
        sum += 0ll+a[x];

    for(auto x:adj[i])
        for(int j=1;j<=100;j++)
            dp[i][j] = max(dp[i][j],max(dp[x][j],dp[x][j-1]+sum));

    ans = max(ans,dp[i][k]);

    for(auto x:adj[i]){
        for(int j=1;j<=100;j++)
            for(int j1=0;j1<2;j1++){
                LL val = dp[x][j-j1];
                if(val>mx[i][j][j1].F){
                    
                    swap(mx[i][j][j1].F,mx[i][j][j1].S);

                    mx[i][j][j1].F = val;
                    mxnode[i][j][j1] = x;
                }
                else 
                    if(val>mx[i][j][j1].S)
                        mx[i][j][j1].S = val;
            }
    }

    for(auto x:adj[i]){
        if(x==pre)continue;

        sum -= 0ll+a[x];
        for(int j=1;j<=100;j++){
            LL val[2] = {0,0};
            for(int j1=0;j1<2;j1++)
                if(mxnode[i][j][j1]==x)
                    val[j1] = mx[i][j][j1].S;
                else 
                    val[j1] = mx[i][j][j1].F;
            dp[i][j] = max(val[0],val[1]+sum);        
        }
        rootshift(x,i);
        sum += 0ll+a[x];
    }

}

int main(){

    //freopen("out.txt","w",stdout);

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,0);
    rootshift(1,0);
    printf("%lld\n",ans);
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
chase.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
chase.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 7 ms 7440 KB Output is correct
8 Correct 7 ms 7500 KB Output is correct
9 Correct 8 ms 7500 KB Output is correct
10 Correct 8 ms 7368 KB Output is correct
11 Correct 8 ms 7372 KB Output is correct
12 Correct 9 ms 7372 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 485952 KB Output is correct
2 Correct 615 ms 486208 KB Output is correct
3 Correct 460 ms 481100 KB Output is correct
4 Correct 611 ms 480980 KB Output is correct
5 Correct 604 ms 480992 KB Output is correct
6 Correct 611 ms 480828 KB Output is correct
7 Correct 609 ms 480832 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 7 ms 7440 KB Output is correct
8 Correct 7 ms 7500 KB Output is correct
9 Correct 8 ms 7500 KB Output is correct
10 Correct 8 ms 7368 KB Output is correct
11 Correct 8 ms 7372 KB Output is correct
12 Correct 9 ms 7372 KB Output is correct
13 Correct 580 ms 485952 KB Output is correct
14 Correct 615 ms 486208 KB Output is correct
15 Correct 460 ms 481100 KB Output is correct
16 Correct 611 ms 480980 KB Output is correct
17 Correct 604 ms 480992 KB Output is correct
18 Correct 611 ms 480828 KB Output is correct
19 Correct 609 ms 480832 KB Output is correct
20 Correct 641 ms 482796 KB Output is correct
21 Correct 621 ms 482676 KB Output is correct
22 Correct 620 ms 482880 KB Output is correct
23 Correct 618 ms 482636 KB Output is correct
24 Correct 667 ms 482628 KB Output is correct
25 Correct 447 ms 482592 KB Output is correct
26 Correct 587 ms 488160 KB Output is correct
27 Correct 546 ms 488132 KB Output is correct