Submission #1204385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204385		liberator	Vinjete (COI22_vinjete)	C++20	0 / 100	3 ms	2884 KiB

Main

#include <iostream>
#include <vector>
#include <array>
#include <set>

#define pb push_back

using namespace std;
using ll = long long;

const int N = 1e5+10;
vector<array<int, 3>> adj[N];
int ans[N];

struct item {
	ll k;
	ll sum;
	int w;
	int cnt;
	item *l, *r;

	ll val() {
		return (k&1) ? -k/2 : k/2;
	}

	item (ll k) : k(k), w(rand()), l(NULL), r(NULL)
	{
		sum = val();
		cnt = 1;
	}
};

typedef item* pitem;
pitem tr;

ll sum(pitem t) {
	return (!t) ? 0ll : t->sum;
}

int cnt(pitem t) {
	return (!t) ? 0 : t->cnt;
}

void recalc(pitem t) {
	if (!t) return;
	t->sum = t->val() + sum(t->l) + sum(t->r);
	t->cnt = 1 + cnt(t->l) + cnt(t->r);
}


void split(pitem t, ll k, pitem &l, pitem &r)
{
	if (!t)
		l = r = NULL;
	else if (t->k <= k) {
		split(t->r, k, t->r, r);
		l = t;
		recalc(l);
	} else {
		split(t->l, k, l, t->l);
		r = t;
		recalc(r);
	}
}

void shave(pitem t, int c, pitem &l, pitem &r)
{
	if (!t)
		l = r = NULL;
	else if (cnt(t->l) < c) {
		shave(t->r, c - cnt(t->l) + 1, t->r, r);
		l = t;
		recalc(l);
	} else {
		shave(t->l, c, l, t->l);
		r = t;
		recalc(r);
	}
}

pitem uni(pitem l, pitem r) {
	if (!l || !r) return l ? l : r;
	if (l->w < r->w) {
		r->l = uni(l, r->l);
		recalc(r);
		return r;
	} else {
		l->r = uni(l->r, r);
		recalc(l);
		return l;
	}
}

pitem adds(int l, int r) {
	r++; /* [l, r) */
	l = 2*l+1;
	r = 2*r;

	pitem pl, pr, tmp;

	split(tr, l, pl, tr);
	split(tr, r, tr, pr);

	if (cnt(pl)&1) {
		shave(pl, cnt(pl) - 1, pl, tmp);
		l = min((ll)l, tmp->k);
		tr = uni(tmp, tr);
	}

	if (cnt(pr)&1) {
		shave(pr, 1, tmp, pr);
		r = max((ll)r, tmp->k);
		tr = uni(tr, tmp);
	}

	pl = uni(pl, new item(l));
	pr = uni(new item(r), pr);
	tmp = tr;
	tr = uni(pl, pr);

	return tmp;
}

void rems(int l, pitem tmp) {
	pitem pl, pr, v;

	split(tr, 2*l+1, pl, pr);
	shave(pl, cnt(pl)-1, pl, v);
	shave(pr, 1, v, pr);

	tr = uni(pl, tmp);
	tr = uni(tr, pr);
}

void dfs(int x, int p) {
	ans[x] = sum(tr);
	pitem tmp;
	for (auto u : adj[x]) {
		if (u[0] == p) continue;
		tmp = adds(u[1], u[2]);
		dfs(u[0], x);
		rems(u[1], tmp);
	}
}

int main() {
	int n, m;
	int a, b, l, r;

	cin >> n >> m;

	for (int i = 1; i < n; i++) {
		cin >> a >> b >> l >> r;
		--a, --b;

		adj[a].pb({b, l, r});
		adj[b].pb({a, l, r});
	}

	dfs(0, 0);

	for (int i = 1; i < n; i++)
		cout << ans[i] << endl;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31