oj.uz

Submission #1024235

# Submission time Handle Problem Language Result Execution time Memory
1024235 2024-07-15T17:48:11 Z vjudge1 Fireworks (APIO16_fireworks) C++17
0 / 100
 4 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 3E2+16, INF = ll(1E18)+16;
vii adj[MAXN];
ll dp[MAXN][MAXN];

void dfs (ll u) {
    if (adj[u].empty()) iota(dp[u], dp[u]+MAXN, 0);
    for (auto [v, w] : adj[u]) {
        dfs(v);
        for (ll i = 0; i <= 300; i++) {
            ll minN = INF;
            for (ll j = 0; j <= 300; j++) {
                minN = min(minN, dp[v][j]+abs(j+w-i));
            }
            dp[u][i] += minN;
        }
    }
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    for (ll v = 1; v < n+m; v++) {
        ll u, w;
        cin >> u >> w;
        u--;
        adj[u].push_back({ v, w });
    }
    dfs(0);
    ll ans = INF;
    for (ll i = 0; i <= 30; i++) {
        cerr << dp[0][i] << ' ';
    }
    cerr << '\n';
    for (ll i = 0; i <= 300; i++) {
        ans = min(ans, dp[0][i]);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Incorrect 4 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 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 600 KB Output isn't correct
2 Halted 0 ms 0 KB -