Submission #1017377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017377		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	238 ms	24588 KiB

fireworks

#include <stdio.h>
const int _(300001);
int d[_], f[_], w[_], r[_];
struct node { int d, lc, rc; long long v; } t[_ << 2];
void swap(int &x, int &y) { x ^= y ^= x ^= y;}
int merge(int x, int y)
{
    if (!x || !y) return x | y;
    if (t[x].v < t[y].v) swap(x, y);
    t[x].rc = merge(t[x].rc, y);
    if (t[t[x].lc].d < t[t[x].rc].d) swap(t[x].lc, t[x].rc);
    t[x].d = t[t[x].rc].d + 1;
    return x;
}
int pop(const int x) { return merge(t[x].lc, t[x].rc); }
int main()
{
    int n, m; scanf("%d%d", &n, &m); long long s(0);
    for (int i(2); i <= n + m; ++i) scanf("%d%d", &f[i], &w[i]), ++d[f[i]], s += w[i];
    for (int i(n + m), j(0); i > 1; --i)
    {
        long long L(0), R(0);
        if (i <= n)
        {
            while (--d[i]) r[i] = pop(r[i]);
            R = t[r[i]].v; r[i] = pop(r[i]);
            L = t[r[i]].v; r[i] = pop(r[i]);
        }
        t[++j].v = L + w[i]; t[++j].v = R + w[i];
        r[i] = merge(r[i], merge(j - 1, j));
        r[f[i]] = merge(r[f[i]], r[i]);
    }
    while (d[1]--) r[1] = pop(r[1]);
    while (r[1]) s -= t[r[1]].v, r[1] = pop(r[1]);
    return !printf("%lld\n", s);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:18:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     int n, m; scanf("%d%d", &n, &m); long long s(0);
      |               ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:19:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for (int i(2); i <= n + m; ++i) scanf("%d%d", &f[i], &w[i]), ++d[f[i]], s += w[i];
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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