Submission #106301

#	Time	Username	Problem	Language	Result	Execution time	Memory
106301		alexpetrescu	Fireworks (APIO16_fireworks)	C++14	26 / 100	20 ms	16896 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];
std::priority_queue < ll > q[MAXN + 1];

void dfs(int x) {
    for (auto &y : g[x]) {
        dfs(y);
        d[x] += d[y];
        while (!q[y].empty()) {
            q[x].push(q[y].top());
            q[y].pop();
        }
    }
    for (int i = g[x].size(); i > bool(c[x]); i--) {
        d[x] += q[x].top();
        q[x].pop();
    }
    if (g[x].empty()) {
        q[x].push(c[x]);
        q[x].push(c[x]);
        d[x] = -c[x];
    } else if (c[x]) {
        int a = q[x].top();
        q[x].pop();
        int b = q[x].top();
        q[x].pop();
        q[x].push(a + c[x]);
        q[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:49: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:54: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: 0 / 29
• Subtask 4: 0 / 45