Submission #128161

#	Time	Username	Problem	Language	Result	Execution time	Memory
128161		srvlt	Fireworks (APIO16_fireworks)	C++14	19 / 100	24 ms	1272 KiB

fireworks

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

const int N = 300, inf = 2e18;
int n, m, dp[N + 3][N + 3];
vector <pair <int, int> > q[N + 3];

void dfs(int v, int p) {
    for (auto i : q[v]) {
        int to = i.fi, w = i.se;
        if (to == p) {
            continue;
        }
        dfs(to, v);
    }
    for (int i = 0; i <= N; i++) {
        int res = 0;
        for (auto j : q[v]) {
            int to = j.fi, w = j.se;
            if (to == p) {
                continue;
            }
            int x = inf;
            for (int k = 0; k <= i; k++) {
                x = min(x, dp[to][i - k] + abs(k - w));
            }
            res += x;
        }
        if (q[v].size() == 1 && v != 1) {
            dp[v][i] = i;
        }   else {
            dp[v][i] = res;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i = 2; i <= n + m; i++) {
        int x, y;
        cin>>x>>y;
        q[x].pb({i, y});
        q[i].pb({x, y});
    }
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            dp[i][j] = inf;
        }
    }
    dfs(1, 1);
    int ans = inf;
    for (int i = 0; i <= N; i++) {
        ans = min(ans, dp[1][i]);
    }
    cout<<ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:19:24: warning: unused variable 'w' [-Wunused-variable]
         int to = i.fi, w = i.se;
                        ^

• Subtask 1: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45