Submission #140567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140567	2019-08-03T14:43:33 Z	eriksuenderhauf	Fireworks (APIO16_fireworks)	C++11	26 / 100	37 ms	31864 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 par[MAXN];
ll a[MAXN], b[MAXN], w[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 %lld", 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];
		merge(par[i], i);
	}
	for (int i = n; i > 1; 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];
		merge(par[i], i);
	}
	while (a[1] > 0) {
		a[1]--;
		b[1] += pq[1].top();
		pq[1].pop();
	}
	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 %lld", par+i, w+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	31608 KB	Output is correct
2	Correct	30 ms	31608 KB	Output is correct
3	Correct	30 ms	31736 KB	Output is correct
4	Correct	30 ms	31608 KB	Output is correct
5	Correct	31 ms	31736 KB	Output is correct
6	Correct	30 ms	31736 KB	Output is correct
7	Correct	30 ms	31608 KB	Output is correct
8	Correct	30 ms	31736 KB	Output is correct
9	Correct	30 ms	31736 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	30 ms	31736 KB	Output is correct
2	Correct	30 ms	31736 KB	Output is correct
3	Correct	30 ms	31736 KB	Output is correct
4	Correct	30 ms	31608 KB	Output is correct
5	Correct	37 ms	31736 KB	Output is correct
6	Correct	33 ms	31736 KB	Output is correct
7	Correct	35 ms	31864 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	30 ms	31608 KB	Output is correct
12	Correct	30 ms	31736 KB	Output is correct
13	Correct	30 ms	31736 KB	Output is correct
14	Correct	30 ms	31608 KB	Output is correct
15	Correct	31 ms	31736 KB	Output is correct
16	Correct	30 ms	31736 KB	Output is correct
17	Correct	35 ms	31736 KB	Output is correct
18	Correct	30 ms	31612 KB	Output is correct
19	Correct	30 ms	31704 KB	Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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

Submission #140567

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