oj.uz

Submission #101616

# Submission time Handle Problem Language Result Execution time Memory
101616 2019-03-19T05:19:19 Z cheeheng Chase (CEOI17_chase) C++14
0 / 100
 103 ms 27316 KB 
#include <bits/stdc++.h>

using namespace std;

long long p[100005];
long long p2[100005];
vector<int> AdjList[100005];

int parent[100005];
vector<int> AdjList2[100005];

int dist[100005];

long long memo[1005][105][2];

long long dp(int u, int b, bool taken){
    if(AdjList2[u].empty()){
        // leaf node
        if(b >= 1 && !taken && parent[u] != -1){
            return p[parent[u]];
        }else{
            return 0;
        }
    }else if(b == 0){
        return 0;
    }else if(memo[u][b][taken] != -1){
        return memo[u][b][taken];
    }else{
        long long temp = 0;
        long long score = 0;
        for(int v: AdjList2[u]){
            score += p[v];
        }

        if(!taken && parent[u] != -1){
            score += p[parent[u]];
        }

        for(int v: AdjList2[u]){
            temp = max(temp, score+dp(v, b-1, 1));
            temp = max(temp, dp(v, b-1, 0));
        }
        return memo[u][b][taken] = temp;
    }
}

int main(){
    int N, v;
    scanf("%d%d", &N, &v);

    for(int i = 1; i <= N; i ++){
        scanf("%d", &p[i]);
        p2[i] = p[i];
    }

    for(int i = 1; i < N; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        AdjList[a].push_back(b);
        AdjList[b].push_back(a);
    }

    long long ans = 0;
    for(int i = 1; i <= N; i ++){
        queue<int> q;
        q.push(i);
        memset(dist, -1, sizeof(dist));
        dist[i] = 0;
        for(int j = 1; j <= N; j ++){
            AdjList2[j].clear();
        }
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v: AdjList[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    AdjList2[u].push_back(v);
                    q.push(v);
                }
            }
        }

        memset(memo, -1, sizeof(memo));
        long long temp = dp(i, v, 1);
        ans = max(ans, temp);
    }

    printf("%lld", ans);
    return 0;
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:52:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &p[i]);
                     ~~~~~^
chase.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &v);
     ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
         ~~~~~^~~~~~~~~~~~~
chase.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Incorrect 11 ms 7040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Incorrect 11 ms 7040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 27316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Incorrect 11 ms 7040 KB Output isn't correct
3 Halted 0 ms 0 KB -