Submission #25581

#	Time	Username	Problem	Language	Result	Execution time	Memory
25581		kajebiii	Fireworks (APIO16_fireworks)	C++14	100 / 100	416 ms	119460 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 3e5 + 100;

int N, M, S[MAX_N], P[MAX_N], C[MAX_N];
vector<pi> Ed[MAX_N];
struct SL {
	priority_queue<ll> Ls;
	priority_queue<ll, vector<ll>, greater<ll> > Rs;
	ll baseL, baseR, ans;
	SL() {
		baseL = baseR = ans = 0;
		while(!Ls.empty()) Ls.pop();
		while(!Rs.empty()) Ls.pop();
	}
	void update() {
		while(Ls.top()+baseL > Rs.top()+baseR) {
			ll a = Ls.top()+baseL;
			ll b = Rs.top()+baseR;
			ans += a-b;
			Ls.pop(); Rs.pop();
			Ls.push(b-baseL); Rs.push(a-baseR);
		}
	}
	void add(ll l, ll r) {
		Ls.push(l-baseL), Rs.push(r-baseR);
		update();
	}
	void add(SL &o) {
		ans += o.ans;
		while(!o.Ls.empty()) Ls.push(o.Ls.top() + o.baseL - baseL), o.Ls.pop();
		while(!o.Rs.empty()) Rs.push(o.Rs.top() + o.baseR - baseR), o.Rs.pop();
		update();
	}
	void addLine(int b) {
		baseR += b; baseL += 0;
		ll l = Ls.top(), r = Rs.top();
		Ls.pop();
		Ls.push(l+b);
		while(!Rs.empty()) Rs.pop();
		Rs.push(r);
		update();
	}
	void print() {
		vector<int> vs;
//		printf("base %lld | ans %lld\n", base, ans);
		while(!Ls.empty()) {
			printf("%lld ", Ls.top()); vs.push_back(Ls.top()); Ls.pop();
		}
		puts("");
		for(int x : vs) Ls.push(x); vs.clear();
		while(!Rs.empty()) {
			printf("%lld ", Rs.top()); vs.push_back(Rs.top()); Rs.pop();
		}
		puts("");		puts("");
		for(int x : vs) Rs.push(x); vs.clear();
	}
};
vector<SL> Ss; int Ix[MAX_N];
void dfs(int v, int p) {
	S[v] = 1;
	int maxV = -1, ix = -1;
	for(pi &e : Ed[v]) {
		int w, c; tie(w, c) = e;
		if(w == p) continue;
		dfs(w, v);
		S[v] += S[w];
		if(maxV < S[w]) maxV = S[w], ix = w;
	}
	if(ix == -1) {
		int c = C[v];
		SL node; node.add(c, c);
		Ix[v] = Ss.size();
		Ss.push_back(node);
	} else {
		Ix[v] = Ix[ix];
		for(pi &e : Ed[v]) {
			int w, c; tie(w, c) = e;
			if(w == p || w == ix) continue;
			Ss[Ix[v]].add(Ss[Ix[w]]);
		}
//		printf("%d : %lld\n", v, Ss[Ix[v]].ans);
		Ss[Ix[v]].addLine(C[v]);
	}
//	printf("[%d] (%d) finish\n", v, Ix[v]); Ss[Ix[v]].print();
}
int main() {
	cin >> N >> M; N += M;
	for(int i=2; i<=N; i++) {
		int p, c; scanf("%d%d", &p, &c);
		P[i] = p; C[i] = c;
		Ed[i].push_back(pi(p, c));
		Ed[p].push_back(pi(i, c));
	}
	dfs(1, 0);
	printf("%lld\n", Ss[Ix[1]].ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:103:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p, c; scanf("%d%d", &p, &c);
                                  ^

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