oj.uz

Submission #26397

# Submission time Handle Problem Language Result Execution time Memory
26397 2017-06-29T20:20:37 Z WhipppedCream Fireworks (APIO16_fireworks) C++14
26 / 100
 0 ms 11392 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long L;
typedef vector< L > vL;
typedef vector< vL > vvL;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
const int inf = 1e9;
const L inf8 = 1e18;
int p[300005], c[300005];
struct node
{
	L a, b;
	priority_queue<L> *pq;
	node operator+(node r)
	{
		node res;
		res.a = a + r.a;
		res.b = b + r.b;
		if(pq->size()> r.pq->size())
		{
			res.pq = pq;
			while(r.pq->size()> 0)
			{
				res.pq->push(r.pq->top()); r.pq->pop();
			}
		}
		else
		{
			res.pq = r.pq;
			while(pq->size()> 0)
			{
				res.pq->push(pq->top()); pq->pop();
			}
		}
		return res;
	}
};
node f[300005];
int main()
{
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 2; i<= n+m; i++) scanf("%d %d", p+i, c+i);
	for(int i = 1; i<= n+m; i++)
	{
		f[i].a = f[i].b = 0;
		f[i].pq = new priority_queue<L>;
	}
	for(int i = n+1; i<= n+m; i++)
	{
		f[i].a = 1; f[i].b = -c[i];
		f[i].pq->push(c[i]); f[i].pq->push(c[i]);
		f[p[i]] = f[p[i]]+f[i];
	}
	for(int i = n; i> 1; i--)
	{
		while(f[i].a> 1)
		{
			f[i].b += f[i].pq->top();
			f[i].pq->pop();
			f[i].a--;
		}
		int k1 = f[i].pq->top(); f[i].pq->pop();
		int k2 = f[i].pq->top(); f[i].pq->pop();
		f[i].pq->push(k1+c[i]); f[i].pq->push(k2+c[i]);
		f[i].b -= c[i];
		f[p[i]] = f[p[i]]+f[i];
	}
	while(f[1].a> 0)
	{
		f[1].a--;
		f[1].b += f[1].pq->top();
		f[1].pq->pop();
	}
	cout << f[1].b << endl;
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:49:34: 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:50:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 2; i<= n+m; i++) scanf("%d %d", p+i, c+i);
                                                       ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11392 KB Output is correct
2 Correct 0 ms 11392 KB Output is correct
3 Correct 0 ms 11392 KB Output is correct
4 Correct 0 ms 11392 KB Output is correct
5 Correct 0 ms 11392 KB Output is correct
6 Correct 0 ms 11392 KB Output is correct
7 Correct 0 ms 11392 KB Output is correct
8 Correct 0 ms 11392 KB Output is correct
9 Correct 0 ms 11392 KB Output is correct
10 Correct 0 ms 11392 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11392 KB Output is correct
2 Correct 0 ms 11392 KB Output is correct
3 Correct 0 ms 11392 KB Output is correct
4 Correct 0 ms 11392 KB Output is correct
5 Correct 0 ms 11392 KB Output is correct
6 Correct 0 ms 11392 KB Output is correct
7 Correct 0 ms 11392 KB Output is correct
8 Correct 0 ms 11392 KB Output is correct
9 Correct 0 ms 11392 KB Output is correct
10 Correct 0 ms 11392 KB Output is correct
11 Correct 0 ms 11392 KB Output is correct
12 Correct 0 ms 11392 KB Output is correct
13 Correct 0 ms 11392 KB Output is correct
14 Correct 0 ms 11392 KB Output is correct
15 Correct 0 ms 11392 KB Output is correct
16 Correct 0 ms 11392 KB Output is correct
17 Correct 0 ms 11392 KB Output is correct
18 Correct 0 ms 11392 KB Output is correct
19 Correct 0 ms 11392 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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