oj.uz

Submission #960851

# Submission time Handle Problem Language Result Execution time Memory
960851 2024-04-11T06:30:12 Z Ghetto Chase (CEOI17_chase) C++17
40 / 100
 72 ms 136520 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e4 + 5, MAX_K = 1e2 + 5;

int n, k;
lint val[MAX_N];
vector<int> adj[MAX_N], adj_ind[MAX_N]; // adj_ind[u][i] = ind of adj list u is for adj[u][i]
void init() {
    for (int i = 1; i <= n; i++) {
        adj[i].push_back(0);
        adj_ind[i].push_back(0);
    }
}

vector<lint> dp[MAX_N][MAX_K];
vector<bool> seen[MAX_N][MAX_K];
void precomp() {
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= k; c++) {
            dp[i][c].resize(adj[i].size() + 2);
            seen[i][c].resize(adj[i].size() + 2);
        }
    }
}

lint find_dp(int u, int c, int prev) {
    if (c == 0) return 0;
    if (seen[u][c][prev]) return dp[u][c][prev];

    lint leave = 0;
    for (int i = 1; i < adj[u].size(); i++)
        if (i != prev) leave = max(leave, find_dp(adj[u][i], c, adj_ind[u][i]));

    lint take = 0;
    for (int i = 1; i < adj[u].size(); i++)
        if (i != prev) take = max(take, find_dp(adj[u][i], c - 1, adj_ind[u][i]));
     for (int i = 1; i < adj[u].size(); i++)
        if (i != prev) take += val[adj[u][i]];

    dp[u][c][prev] = max(take, leave);
    seen[u][c][prev] = true;    
    return dp[u][c][prev];
}

int main() {
    // freopen("chase.in", "r", stdin);

    cin >> n >> k;
    init();

    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);

        int u_ind = adj[u].size() - 1, v_ind = adj[v].size() - 1;
        adj_ind[u].push_back(v_ind);
        adj_ind[v].push_back(u_ind);
    }

    precomp();

    lint ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, find_dp(i, k, 0));
    cout << ans << '\n';
}

Compilation message

chase.cpp: In function 'lint find_dp(int, int, int)':
chase.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 1; i < adj[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
chase.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 1; i < adj[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
chase.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |      for (int i = 1; i < adj[u].size(); i++)
      |                      ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66932 KB Output is correct
2 Correct 19 ms 66652 KB Output is correct
3 Correct 17 ms 66904 KB Output is correct
4 Correct 15 ms 66712 KB Output is correct
5 Correct 18 ms 66652 KB Output is correct
6 Correct 16 ms 66652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66932 KB Output is correct
2 Correct 19 ms 66652 KB Output is correct
3 Correct 17 ms 66904 KB Output is correct
4 Correct 15 ms 66712 KB Output is correct
5 Correct 18 ms 66652 KB Output is correct
6 Correct 16 ms 66652 KB Output is correct
7 Correct 36 ms 75096 KB Output is correct
8 Correct 19 ms 67160 KB Output is correct
9 Correct 47 ms 67164 KB Output is correct
10 Correct 28 ms 74988 KB Output is correct
11 Correct 20 ms 69212 KB Output is correct
12 Correct 19 ms 67616 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 136520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66932 KB Output is correct
2 Correct 19 ms 66652 KB Output is correct
3 Correct 17 ms 66904 KB Output is correct
4 Correct 15 ms 66712 KB Output is correct
5 Correct 18 ms 66652 KB Output is correct
6 Correct 16 ms 66652 KB Output is correct
7 Correct 36 ms 75096 KB Output is correct
8 Correct 19 ms 67160 KB Output is correct
9 Correct 47 ms 67164 KB Output is correct
10 Correct 28 ms 74988 KB Output is correct
11 Correct 20 ms 69212 KB Output is correct
12 Correct 19 ms 67616 KB Output is correct
13 Runtime error 72 ms 136520 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -