oj.uz

Submission #708259

# Submission time Handle Problem Language Result Execution time Memory
708259 2023-03-11T13:00:53 Z four_specks Fireworks (APIO16_fireworks) C++17
7 / 100
 1 ms 316 KB 
#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

void solve()
{
    int n, m;
    cin >> n >> m;

    int k = n + m;

    vector<long> a(k);
    vector<vector<int>> adj(k);
    for (int u = 1; u < k; u++)
    {
        int p;
        cin >> p >> a[u], --p;

        adj[p].push_back(u);
    }

    long res = get<0>(YCombinator(
        [&](auto self, int u) -> tuple<long, priority_queue<long>, priority_queue<long, vector<long>, greater<long>>>
        {
            tuple<long, priority_queue<long>, priority_queue<long, vector<long>, greater<long>>> cost;
            auto &[val, lft, rgt] = cost;

            if (adj[u].empty())
            {
                lft.push(0);
                rgt.push(0);
            }

            for (int v : adj[u])
            {
                tuple cost_v = self(v);
                auto &[val_v, lft_v, rgt_v] = cost_v;

                if ((int)lft.size() + (int)rgt.size() < (int)lft_v.size() + (int)rgt_v.size())
                    swap(cost, cost_v);

                val += val_v;

                while (!lft_v.empty())
                {
                    long x = lft_v.top();
                    lft_v.pop();

                    rgt.push(x);
                    val += x - rgt.top();
                    lft.push(rgt.top());
                    rgt.pop();
                }

                while (!rgt_v.empty())
                {
                    long x = rgt_v.top();
                    rgt_v.pop();

                    lft.push(x);
                    val += lft.top() - x;
                    rgt.push(lft.top());
                    lft.pop();
                }
            }

            lft.push(lft.top() + a[u]);

            {
                long x = rgt.top() + a[u];
                while (!rgt.empty())
                    rgt.pop();
                rgt.push(x);
            }

            return cost;
        })(0));

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 316 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 316 KB Output isn't correct
14 Halted 0 ms 0 KB -