oj.uz

Submission #409274

# Submission time Handle Problem Language Result Execution time Memory
409274 2021-05-20T13:42:57 Z Hazem Chase (CEOI17_chase) C++14
50 / 100
 607 ms 408216 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 a[N],dp[N][M],prevals[N][M];
pii mx[N][M][2],mxnode[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 += 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 += 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);
                    swap(mxnode[i][j][j1].F,mxnode[i][j][j1].S);

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

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

        sum -= 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].F==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 += a[x];
    }
}

int main(){

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

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

    for(int i=1;i<=n;i++)
        scanf("%lld",&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:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
chase.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
chase.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         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 2 ms 2656 KB Output is correct
3 Correct 2 ms 2660 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2660 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 6732 KB Output is correct
8 Incorrect 7 ms 6732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 408216 KB Output is correct
2 Correct 607 ms 408092 KB Output is correct
3 Correct 444 ms 402296 KB Output is correct
4 Correct 599 ms 401968 KB Output is correct
5 Correct 607 ms 401852 KB Output is correct
6 Correct 604 ms 402060 KB Output is correct
7 Correct 599 ms 401864 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2660 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 6732 KB Output is correct
8 Incorrect 7 ms 6732 KB Output isn't correct
9 Halted 0 ms 0 KB -