Submission #869726

#	Time	Username	Problem	Language	Result	Execution time	Memory
869726		luanmenglei	Fireworks (APIO16_fireworks)	C++17	100 / 100	236 ms	24916 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED cerr << "PASSED " << __FUNCTION__ << " #" << __LINE__ << "\n";

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (y < x) x = y; }

const int N = 6e5 + 10;
int n, m, lc[N], rc[N], rt[N], dis[N], a[N], fa[N], cnt, deg[N];
i64 val[N];

int merge(int x, int y) {
	if (!x || !y)
		return x | y;
	if (val[x] < val[y])
		swap(x, y);
	rc[x] = merge(rc[x], y);
	if (dis[lc[x]] < dis[rc[x]])
		swap(lc[x], rc[x]);
	dis[x] = rc[x] ? dis[rc[x]] + 1 : 0;
	return x;
}

void pop(int x) {
	rt[x] = merge(lc[rt[x]], rc[rt[x]]); 
}

void ___solve() {
	cin >> n >> m;
	for (int i = 2; i <= n + m; i ++)
		cin >> fa[i] >> a[i], ++ deg[fa[i]];
	for (int i = n + m; i > 1; i --) {
		i64 l = 0, r = 0;
		if (i <= n) {
			for (int j = 1; j < deg[i]; j ++)
				pop(i);
			r = val[rt[i]];
			pop(i);
			l = val[rt[i]];
			pop(i);
		}
		l += a[i], r += a[i];
		val[++ cnt] = l, val[++ cnt] = r;
		rt[fa[i]] = merge(rt[fa[i]], merge(rt[i], merge(cnt - 1, cnt)));
	}
	for (int j = 1; j <= deg[1]; j ++)
		pop(1);
	i64 ans = 0;
	for (int i = 2; i <= n + m; i ++)
		ans += a[i];
	while (rt[1] > 0) {
		ans -= val[rt[1]], pop(1);
	}
	cout << ans << "\n";
}

}
bool edB;
signed main() {
	// cerr << "Memory: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	SOL::___solve();
	return 0;
}

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