Submission #1175906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175906		andrei_iorgulescu	Fireworks (APIO16_fireworks)	C++20	7 / 100	4 ms	7496 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n, m;
int t[300005], c[300005];
vector<int> f[300005];
vector<int> hs[5005], dp[5005];
int h[5005];

void root(int nod)
{
    for (auto fiu : f[nod])
    {
        h[fiu] = c[fiu] + h[nod];
        root(fiu);
    }
    if (f[nod].empty())
        hs[nod].push_back(h[nod]);
    else
    {
        for (auto fiu : f[nod])
            for (auto it : hs[fiu])
                hs[nod].push_back(it);
    }
}

void calc(int nod)
{
    for (auto fiu : f[nod])
        calc(fiu);
    if (f[nod].empty())
        dp[nod][0] = 0;
    else
    {
        for (int i = 0; i < hs[nod].size(); i++)
        {
            int ct = 0;
            for (int j = 0; j < f[nod].size(); j++)
            {
                int mnm = inf;
                int fiu = f[nod][j];
                for (int q = 0; q < hs[fiu].size(); q++)
                    mnm = min(mnm, abs(hs[fiu][q] - hs[nod][i]) + dp[fiu][q]);
                ct += mnm;
            }
            dp[nod][i] = ct;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    n += m;
    for (int i = 2; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        f[t[i]].push_back(i);
    }
    root(1);
    for (int i = 1; i <= n; i++)
        dp[i].resize(hs[i].size());
    calc(1);
    int mnm = inf;
    for (auto it : dp[1])
        mnm = min(mnm, it);
    cout << mnm;
    return 0;
}

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