Submission #711181

#	Time	Username	Problem	Language	Result	Execution time	Memory
711181		pls33	Fireworks (APIO16_fireworks)	C++17	55 / 100	2063 ms	32476 KiB

fireworks

/*
 * Author: Seokhwan Choi
 * Time Complexity: O((N+M)*log(N+M))
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

#define MAXN 300100
int n, m;
int p[MAXN];
int c[MAXN];
struct ndata
{                       // contains data for subtree (y=f(x), where y is minimum cost when distance to all leaf node is x
    long long int a, b; // y=ax+b at large x
    vi64 *pq;           // saves slope changing points, slope change by 1 at each element
    ndata operator+(ndata r)
    {            // merge two data by adding them
        ndata s; // result(merged data)
        s.a = a + r.a;
        s.b = b + r.b;
        if (pq->size() > r.pq->size())
        { // merge smaller priority queue to larger priority queue
            s.pq = pq;

            s.pq->insert(s.pq->end(), r.pq->begin(), r.pq->end());
            make_heap(s.pq->begin(), s.pq->end());
            r.pq->clear();
        }
        else
        {
            s.pq = r.pq;

            s.pq->insert(s.pq->end(), pq->begin(), pq->end());
            make_heap(s.pq->begin(), s.pq->end());
            pq->clear();
        }
        return s;
    }

    int64_t top()
    {
        return pq->front();
    }

    void pop()
    {
        pop_heap(pq->begin(), pq->end());
        pq->pop_back();
    }

    void push(int64_t val)
    {
        pq->push_back(val);
        push_heap(pq->begin(), pq->end());
    }
};
ndata d[MAXN];
int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("fireworks.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int i;
    scanf("%d%d", &n, &m);
    for (i = 2; i <= n + m; i++)
    {
        scanf("%d%d", &p[i], &c[i]);
    }
    for (i = n + m; i > 0; i--)
    { // initiallize
        d[i].a = 0;
        d[i].b = 0;
        d[i].pq = new vi64();
    }
    for (i = n + m; i > n; i--)
    { // leaf nodes
        d[i].a = 1;
        d[i].b = -c[i];

        d[i].push(c[i]);          // slope is -1 if x<c[i], 1 if x>c[i]
        d[i].push(c[i]);          // slope changes by 2
        d[p[i]] = d[p[i]] + d[i]; // add the data to parent node
    }
    for (i = n; i > 1; i--)
    {
        // add edge to parent node
        while (d[i].a > 1)
        {                         // slope over 1 is useless because we can increase only one edge(edge toward parent node)
            d[i].a--;             // slope decrease by 1
            d[i].b += d[i].top(); // y=ax+b=(a-1)x+(b+x) at slope changing point
            d[i].pop();
        }
        long long int ta = d[i].top(); // increase length of slope -1 part by c[i]
        d[i].pop();
        long long int tb = d[i].top();
        d[i].pop();
        d[i].push(tb + c[i]); // move location of slope 0, 1 part by c[i]
        d[i].push(ta + c[i]);
        d[i].b -= c[i];           // y is decreased by c[i] at sufficiently large x (slope 1 part)
        d[p[i]] = d[p[i]] + d[i]; // add the data to parent node
    }
    while (d[1].a > 0)
    { // root node, y at slope 0 is the answer because it is minimum y
        d[1].a--;
        d[1].b += d[1].top();
        d[1].pop();
    }
    printf("%lld\n", d[1].b);
    return 0;
}

Compilation message (stderr)

fireworks.cpp:13: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
   13 | #pragma region dalykai
      | 
fireworks.cpp:37: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   37 | #pragma endregion
      | 
fireworks.cpp: In function 'int main()':
fireworks.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d%d", &p[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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