oj.uz

답안 #57918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57918 2018-07-16T13:59:17 Z wilwxk Chase (CEOI17_chase) C++11
50 / 100
 4000 ms 182052 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);
                for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-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));
        }
        if(n<=1000) {
            for(int cur=2; cur<=n; cur++) {
                predfs(cur, cur);
                for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-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

chase.cpp: In function 'int main()':
chase.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &n, &x);
         ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:47:38: 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]);
                                 ~~~~~^~~~~~~~~~~~~
chase.cpp:49:28: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 3 ms 2720 KB Output is correct
4 Correct 4 ms 2852 KB Output is correct
5 Correct 5 ms 2912 KB Output is correct
6 Correct 4 ms 2912 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 3 ms 2720 KB Output is correct
4 Correct 4 ms 2852 KB Output is correct
5 Correct 5 ms 2912 KB Output is correct
6 Correct 4 ms 2912 KB Output is correct
7 Execution timed out 4016 ms 4536 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2944 ms 174004 KB Output is correct
2 Correct 2619 ms 176244 KB Output is correct
3 Correct 2005 ms 176244 KB Output is correct
4 Correct 246 ms 176244 KB Output is correct
5 Correct 2918 ms 177932 KB Output is correct
6 Correct 2722 ms 180168 KB Output is correct
7 Correct 2628 ms 182052 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 3 ms 2720 KB Output is correct
4 Correct 4 ms 2852 KB Output is correct
5 Correct 5 ms 2912 KB Output is correct
6 Correct 4 ms 2912 KB Output is correct
7 Execution timed out 4016 ms 4536 KB Time limit exceeded
8 Halted 0 ms 0 KB -