oj.uz

Submission #57903

# Submission time Handle Problem Language Result Execution time Memory
57903 2018-07-16T13:45:35 Z wilwxk Cake (CEOI14_cake) C++11
0 / 100
 312 ms 167052 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int MAXK=102;
vector<int> g[MAXN];
int pai[MAXN], v[MAXN];
long long soma[MAXN], dp[MAXN][MAXK][2];
int n, x;

void predfs(int cur, int p) {
    soma[cur]=0; pai[cur]=p;
    for(auto viz : g[cur]) {
        if(viz==p) continue;
        predfs(viz, cur);
        soma[cur]+=v[viz];
    }
}

long long fazdp(int cur, int k, int flag) {
    if(k<0||(k==0&&flag==0)) return 0;
    if(dp[cur][k][flag]!=-1) return dp[cur][k][flag];
    long long resp=0;

    if(flag) {
        resp=soma[cur];
        for(auto viz : g[cur]) {
            if(viz==pai[cur]) continue;
            resp=max(resp, fazdp(viz, k, 0)+soma[cur]);
            resp=max(resp, fazdp(viz, k-1, 1)+soma[cur]);
        }
    }
    else {
        for(auto viz : g[cur]) {
            if(viz==pai[cur]) continue;
            resp=max(resp, fazdp(viz, k, 0));
            resp=max(resp, fazdp(viz, k-1, 1));
        }
    }

    //printf("%d %d %d -> %lld\n", cur, k, flag, resp);
    return dp[cur][k][flag]=resp;
}

int main() {
    scanf("%d %d", &n, &x);
    for(int i=1; i<=n; i++) scanf("%d", &v[i]);
    for(int i=0; i<n-1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        g[a].push_back(b); g[b].push_back(a);
    }

    long long respf=0;
    for(int cur=1; cur<=1; cur++) {
            predfs(cur, cur);
            memset(dp, -1, sizeof(dp));
            for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
            for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
    }
    if(n<=1000) {
        for(int cur=2; cur<=n; cur++) {
            predfs(cur, cur);
            memset(dp, -1, sizeof(dp));
            respf=max(respf, max(fazdp(cur, x, 0), fazdp(cur, x-1, 1)));
            //for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
            //for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
        }
    }


    printf("%lld\n", respf);

}
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &x);
     ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n; i++) scanf("%d", &v[i]);
                             ~~~~~^~~~~~~~~~~~~
cake.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 14 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 21 ms 162552 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 166708 KB Output isn't correct
2 Incorrect 170 ms 166708 KB Output isn't correct
3 Incorrect 154 ms 166756 KB Output isn't correct
4 Incorrect 312 ms 166756 KB Output isn't correct
5 Runtime error 85 ms 166756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 58 ms 166756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 42 ms 166756 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 166756 KB Output isn't correct
2 Incorrect 121 ms 166756 KB Output isn't correct
3 Incorrect 169 ms 167052 KB Output isn't correct
4 Incorrect 151 ms 167052 KB Output isn't correct
5 Runtime error 11 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 34 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 17 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 54 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 15 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 15 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 43 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 84 ms 167052 KB Execution killed with signal 11 (could be triggered by violating memory limits)