oj.uz

Submission #558669

# Submission time Handle Problem Language Result Execution time Memory
558669 2022-05-08T02:54:51 Z hoanghq2004 Fireworks (APIO16_fireworks) C++14
19 / 100
 18 ms 688 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("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 = 3e2 + 10;

int n, m;
vector <pair <int, int> > g[N];
int f[N][N];
int cur[N];

void dfs(int u, int p) {
    if (g[u].empty()) {
        for (int i = 0; i <= 300; ++i) f[u][i] = i;
        return;
    }
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        memset(cur, 60, sizeof(cur));
        for (int i = 0; i <= 300; ++i) {
            for (int j = 0; j <= i; ++j)
                cur[i] = min(cur[i], f[v][j] + abs(i - (w + j)));
        }
        for (int i = 0; i <= 300; ++i) f[u][i] += cur[i];
    }
}

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

Compilation message

fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for (auto [v, w]: g[u]) {
      |               ^

Subtask #1
0 / 7.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 400 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 7 ms 480 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 8 ms 528 KB Output is correct
8 Correct 10 ms 468 KB Output is correct
9 Correct 11 ms 468 KB Output is correct
10 Correct 12 ms 596 KB Output is correct
11 Correct 16 ms 620 KB Output is correct
12 Correct 15 ms 588 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 17 ms 644 KB Output is correct
15 Correct 18 ms 688 KB Output is correct
16 Correct 18 ms 596 KB Output is correct
17 Correct 16 ms 596 KB Output is correct
18 Correct 15 ms 596 KB Output is correct
19 Correct 15 ms 684 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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