Submission #48090

#	Time	Username	Problem	Language	Result	Execution time	Memory
48090		jeff	Fireworks (APIO16_fireworks)	C++14	100 / 100	343 ms	94584 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

long long N, M, l[300000], r[300000];
priority_queue<long long> pq[300000];
vector<long long> adj[300000];

void it(long long i) {
    if (i + 1 > N) {
        pq[i].push(l[i]);
        pq[i].push(l[i]);
        r[i] = -l[i];
        return;
    }
    long long x = 0, z, j;
    pair<long long, long long> p = make_pair(0, 0);
    for (j = 0; j < adj[i].size(); ++j) {
        it(adj[i][j]);
        x = max(x, pq[adj[i][j]].top());
        p = max(p, make_pair((long long) pq[adj[i][j]].size(), j));
    }
    swap(r[i], r[adj[i][p.second]]);
    swap(pq[i], pq[adj[i][p.second]]);
    z = x + r[i];
    for (j = 0; j < adj[i].size(); ++j) if (p.second != j) {
        z += x + r[adj[i][j]];
        while (!pq[adj[i][j]].empty()) pq[i].push(pq[adj[i][j]].top()), pq[adj[i][j]].pop();
    }
    r[i] = z - adj[i].size() * x;
    for (j = 0; j < adj[i].size() - 1; ++j) r[i] += pq[i].top(), pq[i].pop();
    x = pq[i].top();
    pq[i].pop();
    z = pq[i].top();
    pq[i].pop();
    pq[i].push(x + l[i]);
    pq[i].push(z + l[i]);
    r[i] -= l[i];
}

int main() {
    long long a, b, i;
    scanf("%lld %lld", &N, &M);
    for (i = 1; i < N + M; ++i) scanf("%lld %lld", &a, &b), adj[--a].push_back(i), l[i] = b;
    it(0);
    printf("%lld", pq[0].top() + r[0]);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void it(long long int)':
fireworks.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < adj[i].size(); ++j) {
                 ~~^~~~~~~~~~~~~~~
fireworks.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < adj[i].size(); ++j) if (p.second != j) {
                 ~~^~~~~~~~~~~~~~~
fireworks.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < adj[i].size() - 1; ++j) r[i] += pq[i].top(), pq[i].pop();
                 ~~^~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:43:82: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 1; i < N + M; ++i) scanf("%lld %lld", &a, &b), adj[--a].push_back(i), l[i] = b;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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