Submission #106302

#	Time	Username	Problem	Language	Result	Execution time	Memory
106302		alexpetrescu	Fireworks (APIO16_fireworks)	C++14	100 / 100	455 ms	73416 KiB

fireworks

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define ll long long

#define MAXN 300000

std::vector < int > g[MAXN + 1];
ll d[MAXN + 1];
int c[MAXN + 1], k, u[MAXN + 1];
std::priority_queue < ll > q[MAXN + 1];

void dfs(int x) {
    for (auto &y : g[x]) {
        dfs(y);
        d[x] += d[y];
        if (q[u[y]].size() > q[u[x]].size())
            u[x] = u[y];
    }
    for (auto &y : g[x]) {
        if (u[x] != u[y]) {
            while (!q[u[y]].empty()) {
                q[u[x]].push(q[u[y]].top());
                q[u[y]].pop();
            }
        }
    }
    for (int i = g[x].size(); i > bool(c[x]); i--) {
        d[x] += q[u[x]].top();
        q[u[x]].pop();
    }
    if (g[x].empty()) {
        u[x] = ++k;
        q[u[x]].push(c[x]);
        q[u[x]].push(c[x]);
        d[x] = -c[x];
    } else if (c[x]) {
        ll a = q[u[x]].top();
        q[u[x]].pop();
        ll b = q[u[x]].top();
        q[u[x]].pop();
        q[u[x]].push(a + c[x]);
        q[u[x]].push(b + c[x]);
        d[x] -= c[x];
    }
}

int main() {
    int n, m;
    fscanf(fin, "%d%d", &n, &m);
    n += m;

    for (int i = 2; i <= n; i++) {
        int x;
        fscanf(fin, "%d%d", &x, &c[i]);
        g[x].push_back(i);
    }

    dfs(1);

    fprintf(fout, "%lld\n", d[1]);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:56:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d", &n, &m);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:61:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d", &x, &c[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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