oj.uz

Submission #409207

# Submission time Handle Problem Language Result Execution time Memory
409207 2021-05-20T11:02:42 Z Hazem Chase (CEOI17_chase) C++14
30 / 100
 208 ms 172448 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 = 2e5+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 4294967296;
const double PI = 3.141592653589793;

LL a[N],dp[N][M];
vector<int>adj[N];

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));
    }
}

int main(){

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

    int n,k;
    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);
    printf("%lld\n",dp[1][k]);
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 136624 KB Output is correct
2 Correct 175 ms 136468 KB Output is correct
3 Correct 93 ms 11840 KB Output is correct
4 Correct 204 ms 171728 KB Output is correct
5 Correct 204 ms 172448 KB Output is correct
6 Correct 208 ms 171716 KB Output is correct
7 Correct 203 ms 171776 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -