oj.uz

Submission #58089

# Submission time Handle Problem Language Result Execution time Memory
58089 2018-07-16T19:13:24 Z wilwxk Chase (CEOI17_chase) C++11
50 / 100
 4000 ms 171908 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;
}
#define gc getchar_unlocked
inline int scan(){
    int n=0, x=gc(), s=1;
    for(;x<'0'||x>'9';x=gc()) if(x == '-') s = -1;
    for(;x>='0'&&x<='9';x=gc()) n = (n<<1) + (n<<3) + x - '0';
    return n*s;
}


int main() {
    n = scan(), x = scan();
    for(int i=1; i<=n; i++) v[i] = scan();
    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));
            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);

}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:57: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 162424 KB Output is correct
2 Correct 445 ms 162424 KB Output is correct
3 Correct 445 ms 162460 KB Output is correct
4 Correct 453 ms 162488 KB Output is correct
5 Correct 446 ms 162604 KB Output is correct
6 Correct 436 ms 162604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 162424 KB Output is correct
2 Correct 445 ms 162424 KB Output is correct
3 Correct 445 ms 162460 KB Output is correct
4 Correct 453 ms 162488 KB Output is correct
5 Correct 446 ms 162604 KB Output is correct
6 Correct 436 ms 162604 KB Output is correct
7 Execution timed out 4035 ms 162604 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3006 ms 171880 KB Output is correct
2 Correct 2402 ms 171908 KB Output is correct
3 Correct 1721 ms 171908 KB Output is correct
4 Correct 196 ms 171908 KB Output is correct
5 Correct 2746 ms 171908 KB Output is correct
6 Correct 2629 ms 171908 KB Output is correct
7 Correct 3382 ms 171908 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 162424 KB Output is correct
2 Correct 445 ms 162424 KB Output is correct
3 Correct 445 ms 162460 KB Output is correct
4 Correct 453 ms 162488 KB Output is correct
5 Correct 446 ms 162604 KB Output is correct
6 Correct 436 ms 162604 KB Output is correct
7 Execution timed out 4035 ms 162604 KB Time limit exceeded
8 Halted 0 ms 0 KB -