Submission #43074

#	Time	Username	Problem	Language	Result	Execution time	Memory
43074		ekrem	Fireworks (APIO16_fireworks)	C++98	55 / 100	2086 ms	524288 KiB

fireworks

/*
ID: ekrem
LANG: C++
TASK: Fireworks
*/
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;
#define foreach(kk,gg) for(__typeof(gg.begin())kk=gg.begin();kk!=gg.end();kk++)
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define SET(a, b) memset(a, b, sizeof a)
#define heap priority_queue
#define orta (bas+son>>1)
#define endll puts("")
#define mp make_pair
#define pb push_back
#define sag (k+k+1)
#define sol (k+k)
#define endl '\n'
#define nd second
#define st first
#define y1 ekrem
#define y2 merke
typedef int don;
#define int long long int
inline int read(){int x;scanf(" %lld",&x);return x;}

typedef pair < int , int > ii;
typedef vector < int > vi;
typedef vector < ii > vii;

const int inf = 1e9 + 7;
const int linf = 1e18 + 7;

const int N = 3e5 + 5;

int n, m, p[N], c[N], a[N], b[N];
heap < int > h[N];

void ekle(int par, int coc){
	a[par] += a[coc];
	b[par] += b[coc];
	if(h[coc].size() > h[par].size())
		swap(h[par], h[coc]);
	while(!h[coc].empty()){
		h[par].push(h[coc].top());h[coc].pop();
	}
}

don main(){
	// freopen("input.in", "r", stdin);freopen("input.out", "w", stdout);
	n = read();
	m = read();
	FOR(i, 2, n + m){
		p[i] = read();
		c[i] = read();
	}
	ROF(i, n + m, n + 1){//Yapraklar
		a[i] = 1;
		b[i] = -c[i];
		h[i].push(c[i]);
		h[i].push(c[i]);
		ekle(p[i], i);
	}
	ROF(i, n, 2){
		while(a[i] > 1){
			a[i]--;
			b[i] += h[i].top();h[i].pop();
		}
		int bir = h[i].top();h[i].pop();
		int iki = h[i].top();h[i].pop();
		h[i].push(bir + c[i]);
		h[i].push(iki + c[i]);
		b[i] -= c[i];//Bu ne
		ekle(p[i], i);
	}
	while(a[1] > 0){
		a[1]--;
		b[1] += h[1].top();h[1].pop();
	}
	cout << b[1] << endl;
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'long long int read()':
fireworks.cpp:45:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 inline int read(){int x;scanf(" %lld",&x);return x;}
                                          ^

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