oj.uz

Submission #519347

# Submission time Handle Problem Language Result Execution time Memory
519347 2022-01-26T08:42:56 Z hoanghq2004 Chase (CEOI17_chase) C++14
0 / 100
 119 ms 55200 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int n, m;
int f[N][110];
int c[N];
vector <int> g[N];

void dfs(int u, int p) {
    int tot = 0;
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        tot += c[v];
    }
    f[u][1] = tot;
    for (auto v: g[u]) {
        if (v == p) continue;
        for (int i = 0; i <= m; ++i) {
            f[u][i] = max(f[u][i], f[v][i]);
            f[u][i + 1] = max(f[u][i + 1], f[v][i] + tot - c[v]);
        }
    }
    for (int i = 1; i <= m; ++i) f[u][i] = max(f[u][i], f[u][i - 1]);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << f[1][m];
}

Compilation message

chase.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
chase.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 55200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -