Submission #140566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140566	2019-08-03T14:40:08 Z	eriksuenderhauf	Fireworks (APIO16_fireworks)	C++11	26 / 100	37 ms	31740 KB

fireworks

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
priority_queue<ll> pq[MAXN];
int w[MAXN], par[MAXN];
ll a[MAXN], b[MAXN];

void merge(int p, int u) {
	if (pq[p].size() < pq[u].size()) swap(pq[p], pq[u]);
	while (!pq[u].empty()) {
		pq[p].push(pq[u].top());
		pq[u].pop();
	}
	a[p] += a[u]; b[p] += b[u];
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 2; i <= n+m; i++)
		scanf("%d %d", par+i, w+i);
	for (int i = n+m; i > n; i--) {
		pq[i].push(w[i]);
		pq[i].push(w[i]);
		a[i] = 1;
		b[i] = -w[i];
		if (par[i]) merge(par[i], i);
	}
	for (int i = n; i; i--) {
		while (a[i] > 1) {
			a[i]--;
			b[i] += pq[i].top();
			pq[i].pop();
		}
		int x = pq[i].top(); pq[i].pop();
		int y = pq[i].top(); pq[i].pop();
		x += w[i], y += w[i];
		pq[i].push(x); pq[i].push(y);
		b[i] -= w[i];
		if (par[i]) merge(par[i], i);
	}
	while (a[1] > 0) {
		a[1]--;
		b[1] += pq[1].top();
	}
	prl(b[1]);
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d %d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", par+i, w+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31736 KB	Output is correct
2	Correct	31 ms	31608 KB	Output is correct
3	Correct	30 ms	31608 KB	Output is correct
4	Correct	31 ms	31736 KB	Output is correct
5	Correct	30 ms	31736 KB	Output is correct
6	Correct	31 ms	31696 KB	Output is correct
7	Correct	30 ms	31736 KB	Output is correct
8	Correct	30 ms	31736 KB	Output is correct
9	Correct	30 ms	31608 KB	Output is correct
10	Correct	30 ms	31736 KB	Output is correct

Subtask #2
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31608 KB	Output is correct
2	Correct	31 ms	31736 KB	Output is correct
3	Correct	37 ms	31736 KB	Output is correct
4	Correct	37 ms	31736 KB	Output is correct
5	Correct	30 ms	31736 KB	Output is correct
6	Correct	37 ms	31736 KB	Output is correct
7	Correct	32 ms	31708 KB	Output is correct
8	Correct	30 ms	31608 KB	Output is correct
9	Correct	31 ms	31708 KB	Output is correct
10	Correct	30 ms	31736 KB	Output is correct
11	Correct	30 ms	31736 KB	Output is correct
12	Correct	32 ms	31736 KB	Output is correct
13	Correct	30 ms	31736 KB	Output is correct
14	Correct	31 ms	31736 KB	Output is correct
15	Correct	30 ms	31736 KB	Output is correct
16	Correct	30 ms	31740 KB	Output is correct
17	Correct	30 ms	31736 KB	Output is correct
18	Correct	31 ms	31608 KB	Output is correct
19	Correct	30 ms	31736 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31736 KB	Output is correct
2	Correct	31 ms	31608 KB	Output is correct
3	Correct	30 ms	31608 KB	Output is correct
4	Correct	31 ms	31736 KB	Output is correct
5	Correct	30 ms	31736 KB	Output is correct
6	Correct	31 ms	31696 KB	Output is correct
7	Correct	30 ms	31736 KB	Output is correct
8	Correct	30 ms	31736 KB	Output is correct
9	Correct	30 ms	31608 KB	Output is correct
10	Correct	30 ms	31736 KB	Output is correct
11	Correct	31 ms	31608 KB	Output is correct
12	Correct	31 ms	31736 KB	Output is correct
13	Correct	37 ms	31736 KB	Output is correct
14	Correct	37 ms	31736 KB	Output is correct
15	Correct	30 ms	31736 KB	Output is correct
16	Correct	37 ms	31736 KB	Output is correct
17	Correct	32 ms	31708 KB	Output is correct
18	Correct	30 ms	31608 KB	Output is correct
19	Correct	31 ms	31708 KB	Output is correct
20	Correct	30 ms	31736 KB	Output is correct
21	Correct	30 ms	31736 KB	Output is correct
22	Correct	32 ms	31736 KB	Output is correct
23	Correct	30 ms	31736 KB	Output is correct
24	Correct	31 ms	31736 KB	Output is correct
25	Correct	30 ms	31736 KB	Output is correct
26	Correct	30 ms	31740 KB	Output is correct
27	Correct	30 ms	31736 KB	Output is correct
28	Correct	31 ms	31608 KB	Output is correct
29	Correct	30 ms	31736 KB	Output is correct
30	Incorrect	32 ms	31736 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31736 KB	Output is correct
2	Correct	31 ms	31608 KB	Output is correct
3	Correct	30 ms	31608 KB	Output is correct
4	Correct	31 ms	31736 KB	Output is correct
5	Correct	30 ms	31736 KB	Output is correct
6	Correct	31 ms	31696 KB	Output is correct
7	Correct	30 ms	31736 KB	Output is correct
8	Correct	30 ms	31736 KB	Output is correct
9	Correct	30 ms	31608 KB	Output is correct
10	Correct	30 ms	31736 KB	Output is correct
11	Correct	31 ms	31608 KB	Output is correct
12	Correct	31 ms	31736 KB	Output is correct
13	Correct	37 ms	31736 KB	Output is correct
14	Correct	37 ms	31736 KB	Output is correct
15	Correct	30 ms	31736 KB	Output is correct
16	Correct	37 ms	31736 KB	Output is correct
17	Correct	32 ms	31708 KB	Output is correct
18	Correct	30 ms	31608 KB	Output is correct
19	Correct	31 ms	31708 KB	Output is correct
20	Correct	30 ms	31736 KB	Output is correct
21	Correct	30 ms	31736 KB	Output is correct
22	Correct	32 ms	31736 KB	Output is correct
23	Correct	30 ms	31736 KB	Output is correct
24	Correct	31 ms	31736 KB	Output is correct
25	Correct	30 ms	31736 KB	Output is correct
26	Correct	30 ms	31740 KB	Output is correct
27	Correct	30 ms	31736 KB	Output is correct
28	Correct	31 ms	31608 KB	Output is correct
29	Correct	30 ms	31736 KB	Output is correct
30	Incorrect	32 ms	31736 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Submission #140566

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0