oj.uz

Submission #409275

# Submission time Handle Problem Language Result Execution time Memory
409275 2021-05-20T13:44:03 Z Hazem Chase (CEOI17_chase) C++14
40 / 100
 539 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<LL,LL>
#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 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 2 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 9 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct
10 Correct 9 ms 9804 KB Output is correct
11 Correct 9 ms 9800 KB Output is correct
12 Correct 10 ms 9804 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 539 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 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 9 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct
10 Correct 9 ms 9804 KB Output is correct
11 Correct 9 ms 9800 KB Output is correct
12 Correct 10 ms 9804 KB Output is correct
13 Runtime error 539 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -