Submission #1017246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017246		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	234 ms	37976 KiB

fireworks

#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 1e6 + 19;
int f[N], w[N], d[N], root[N];
struct LeftTree {
	int val[N], t[N], ls[N], rs[N], cnt;
	int build_new(int v) {
		val[++cnt] = v;
		return cnt;
	}
	int merge(int p, int q) {
		if (!p || !q) return p + q;
		if (val[p] < val[q]) swap(p, q);
		rs[p] = merge(rs[p], q);
		if (t[ls[p]] < t[rs[p]]) swap(ls[p], rs[p]);
		t[p] = t[rs[p]] + 1;
		return p;
	}
	void del(int &p) {
		p = merge(ls[p], rs[p]);
	}
} tr;
signed main() {
	int n, m, ans = 0;
	read(n, m);
	for (int i = 2; i <= n + m; ++i) {
		read(f[i], w[i]);
		ans += w[i];
		d[f[i]]++;
	}
	for (int u = n + m; u >= 2; --u) {
		if (u <= n) while (--d[u]) tr.del(root[u]);
		int R = tr.val[root[u]]; tr.del(root[u]);
		int L = tr.val[root[u]]; tr.del(root[u]);
		root[u] = tr.merge(root[u], tr.merge(tr.build_new(L + w[u]), tr.build_new(R + w[u])));
		root[f[u]] = tr.merge(root[f[u]], root[u]);
	}
	while (d[1]--) tr.del(root[1]);
	while (root[1]) ans -= tr.val[root[1]], tr.del(root[1]);
	write(ans, '\n');
	return 0;
}

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