Submission #108388

#	Time	Username	Problem	Language	Result	Execution time	Memory
108388		kuroni	Fireworks (APIO16_fireworks)	C++17	100 / 100	303 ms	44096 KiB

fireworks

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int MX = 300005;

int n, m, p[MX], c[MX];

struct TSlope
{
    priority_queue<long long> pq;
    long long a, b;

    TSlope()
    {
        while (!pq.empty())
            pq.pop();
        a = b = 0;
    }

    void pop()
    {
        a--;
        b += pq.top();
        pq.pop();
    }
} sl[MX];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++)
        scanf("%d%d", p + i, c + i);
    for (int i = n + m; i >= 2; i--)
    {
        TSlope &cur = sl[i], &par = sl[p[i]];
        if (i > n)
        {
            cur.pq.push(c[i]); cur.pq.push(c[i]);
            cur.a = 1; cur.b = -c[i];
        }
        else
        {
            while (cur.a > 1)
                cur.pop();
            long long u = cur.pq.top(); cur.pq.pop();
            long long v = cur.pq.top(); cur.pq.pop();
            cur.pq.push(u + c[i]); cur.pq.push(v + c[i]);
            cur.b -= c[i];
        }
        if (par.pq.size() < cur.pq.size())
            swap(par, cur);
        while (!cur.pq.empty())
        {
            par.pq.push(cur.pq.top());
            cur.pq.pop();
        }
        par.a += cur.a; par.b += cur.b;
    }
    TSlope &cur = sl[1];
    while (cur.a > 0)
        cur.pop();
    printf("%lld\n", cur.a * cur.pq.top() + cur.b);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", p + i, c + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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