oj.uz

Submission #310761

# Submission time Handle Problem Language Result Execution time Memory
310761 2020-10-07T20:31:37 Z ly20 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 101404 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 112;
vector <int> grafo[MAXN];
long long val[MAXN], vz[MAXN], dp[MAXN][MAXK];
int n, k;
long long resp;
void dfs(int v, int p) {
    for(int i = 0; i <= k; i++) resp = max(resp, dp[v][i]);
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i];
        if(viz == p) continue;
        dp[viz][0] = 0;
        for(int j = 1; j <= k; j++) {
            dp[viz][j] = max(dp[v][j], dp[v][j - 1] + vz[viz] - val[v]);
        }
        dfs(viz, v);
    }
}
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &val[i]);
    }
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        grafo[a].push_back(b); grafo[b].push_back(a);
        vz[a] += val[b]; vz[b] += val[a];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        for(int j = 1; j <= k; j++) dp[i][j] = vz[i];
        dfs(i, 0);
    }
    printf("%lld\n", resp);
    return 0;
}

Compilation message

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%lld", &val[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 2944 KB Output is correct
3 Correct 2 ms 3072 KB Output is correct
4 Correct 2 ms 2944 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 3072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 2944 KB Output is correct
3 Correct 2 ms 3072 KB Output is correct
4 Correct 2 ms 2944 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 3072 KB Output is correct
7 Correct 275 ms 3968 KB Output is correct
8 Correct 35 ms 3968 KB Output is correct
9 Correct 28 ms 3968 KB Output is correct
10 Correct 284 ms 3968 KB Output is correct
11 Correct 109 ms 3968 KB Output is correct
12 Correct 50 ms 4088 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 101404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 2944 KB Output is correct
3 Correct 2 ms 3072 KB Output is correct
4 Correct 2 ms 2944 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 3072 KB Output is correct
7 Correct 275 ms 3968 KB Output is correct
8 Correct 35 ms 3968 KB Output is correct
9 Correct 28 ms 3968 KB Output is correct
10 Correct 284 ms 3968 KB Output is correct
11 Correct 109 ms 3968 KB Output is correct
12 Correct 50 ms 4088 KB Output is correct
13 Execution timed out 4043 ms 101404 KB Time limit exceeded
14 Halted 0 ms 0 KB -