Submission #284992

#	Time	Username	Problem	Language	Result	Execution time	Memory
284992		Kastanda	Fireworks (APIO16_fireworks)	C++11	100 / 100	281 ms	52608 KiB

fireworks

// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005;
int n, m, P[N], C[N];
vector < int > Ch[N];
priority_queue < ll > PQ[N];
int main()
{
        scanf("%d%d", &n, &m);
        for (int i = 2; i <= n + m; i ++)
                scanf("%d%d", &P[i], &C[i]), Ch[P[i]].push_back(i);
        for (int v = n + m; v; v --)
        {
                if (!Ch[v].size())
                {
                        PQ[v].push(C[v]);
                        PQ[v].push(C[v]);
                        continue;
                }
                for (int u : Ch[v])
                {
                        if (PQ[v].size() < PQ[u].size())
                                PQ[v].swap(PQ[u]);
                        while (PQ[u].size())
                                PQ[v].push(PQ[u].top()), PQ[u].pop();
                }
                for (int i = 0; i < (int)Ch[v].size() - 1; i ++)
                        PQ[v].pop(); // Note that now there are extra positive slopes other than +1.
                // Only the intervals with slope equal to 0 or 1 shift C[v] units to the right.
                ll slope1 = PQ[v].top(); PQ[v].pop();
                ll slope0 = PQ[v].top(); PQ[v].pop();
                PQ[v].push(slope0 + C[v]);
                PQ[v].push(slope1 + C[v]);
        }
        PQ[1].pop(); // Getting rid of the interval with slope +1.
        ll SM = 0; // SM is the value of F(0).
        for (int v = 1; v <= n + m; v ++)
                SM += C[v];
        vector < ll > V;
        while (PQ[1].size())
                V.push_back(PQ[1].top()), PQ[1].pop();
        V.push_back(0);
        reverse(V.begin(), V.end());
        for (int i = 1; i < (int)V.size(); i ++)
                SM -= (V[i] - V[i - 1]) * ((int)V.size() - i);
        return !printf("%lld\n", SM);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:13:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |                 scanf("%d%d", &P[i], &C[i]), Ch[P[i]].push_back(i);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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