That was the way I used to build a centroid tree (a tree that connects all the adjacent centroids during centroid decomposition, used in 342E - Xenia and Tree):

ll n, ctroot, ctp[MAXN];
vector<ll> e[MAXN], ct[MAXN];
namespace centree {
	ll sz[MAXN], mxs[MAXN];
	bool vis[MAXN];
	void clear(ll x, ll pr) {
		sz[x] = mxs[x] = 0, mxs[0] = inf;
		for (ll i : e[x]) {
			if (i == pr || vis[i]) {
				continue;
			}
			clear(i, x);
		}
	}
	void setsz(ll x, ll pr) {
		sz[x] = 1;
		for (ll i : e[x]) {
			if (i == pr || vis[i]) {
				continue;
			}
			setsz(i, x);
			sz[x] += sz[i];
			mxs[x] = max(mxs[x], sz[i]);
		}
	}
	void fndct(ll x, ll pr, ll crt, ll &ret) {
		mxs[x] = max(mxs[x], sz[crt] - sz[x]);
		if (mxs[ret] > mxs[x]) {
			ret = x;
		}
		for (ll i : e[x]) {
			if (i == pr || vis[i]) {
				continue;
			}
			fndct(i, x, crt, ret);
		}
	}
	void bdct(ll x, ll pr) {
		ll cur = 0;
		clear(x, pr), setsz(x, pr), fndct(x, pr, x, cur);
		if (pr) {
			ct[pr].empb(cur);
			ctp[cur] = pr;
		} else {
			ctroot = cur;
		}
		vis[cur] = 1;
		for (ll i : e[cur]) {
			if (i == pr || vis[i]) {
				continue;
			}
			bdct(i, cur);
		}
	}
}

Then I found there were too many for (ll i : e[x]) if (i == pr || vis[i]) continue;s, so I used a macro to do shorten them:

ll n, ctroot, ctp[MAXN];
vector<ll> e[MAXN], ct[MAXN];
namespace centree {
	#define tra(x) for (ll i : e[x]) if (i != pr && !vis[i])
	ll sz[MAXN], mxs[MAXN];
	bool vis[MAXN];
	void clear(ll x, ll pr) {
		sz[x] = mxs[x] = 0, mxs[0] = inf;
		tra(x) {
			clear(i, x);
		}
	}
	void setsz(ll x, ll pr) {
		sz[x] = 1;
		tra(x) {
			setsz(i, x);
			sz[x] += sz[i];
			mxs[x] = max(mxs[x], sz[i]);
		}
	}
	void fndct(ll x, ll pr, ll crt, ll &ret) {
		mxs[x] = max(mxs[x], sz[crt] - sz[x]);
		if (mxs[ret] > mxs[x]) {
			ret = x;
		}
		tra(x) {
			fndct(i, x, crt, ret);
		}
	}
	void bdct(ll x, ll pr) {
		ll cur = 0;
		clear(x, pr), setsz(x, pr), fndct(x, pr, x, cur);
		if (pr) {
			ct[pr].empb(cur);
			ctp[cur] = pr;
		} else {
			ctroot = cur;
		}
		vis[cur] = 1;
		tra(cur) {
			bdct(i, cur);
		}
	}
	#undef tra
}

This reduces my code for about 150 bytes. But what I'm worrying now is: will macros increase the difficulty to debug my code, especially in some on-site contests, where templates are not allowed?

I also used #define mid ((lx+rx)>>1) #define l(x) ((x)<<1) #define r(X) (l(x)|1) in segment tree for months btw

can do almost any 2200* in problemset, but not in a contest, what should i do

627C - Package Delivery

code:

#include <bits/stdc++.h>
using namespace std;
#define emp emplace
#define empb emplace_back
#define umap unordered_map
#define mkp make_pair
typedef long long ll;
typedef pair<ll, ll> pll;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
typedef long double ldb;
const ll MAXN = 5e5 + 5;
mt19937_64 rd(chrono::high_resolution_clock().now().time_since_epoch().count());

#pragma GCC optimize(1,2,3,"Ofast","inline")

istream& operator>>(istream& in, __int128& x) {
	string s;
	in >> s;
	x = 0;
	for (char c : s) {
		x = x * 10 + c - 48;
	}
	return in;
}
ostream& operator<<(ostream& out, __int128 x) {
	if (!x) {
		out << "0";
		return out;
	}
	stack<char> s;
	while (x) {
		s.emp(x % 10 + 48);
		x /= 10;
	}
	while (!s.empty()) {
		out << s.top();
		s.pop();
	}
	return out;
}

struct segtree {
	ll V, l[MAXN], r[MAXN], fr[MAXN], mn[MAXN], rt, size;
	void init(ll x) {
		V = x;
		memset(l, 0, sizeof l);
		memset(r, 0, sizeof r);
		memset(fr, -1, sizeof fr);
		memset(mn, inf, sizeof mn);
		rt = 0;
		size = 0;
	}
	#define mid ((lx+rx)>>1)
	void psu(ll x) {
		if (mn[l[x]] <= mn[r[x]]) fr[x] = fr[l[x]], mn[x] = mn[l[x]];
		else fr[x] = fr[r[x]], mn[x] = mn[r[x]];
	}
	void mdf(ll p, ll v, ll& x, ll lx, ll rx) {
		if (p < lx || p > rx) return;
		if (!x) x = ++size;
		if (lx == rx) {
			fr[x] = p, mn[x] = v;
			return;
		}
		mdf(p, v, l[x], lx, mid), mdf(p, v, r[x], mid + 1, rx);
		psu(x);
	}
	void mdf(ll p, ll v) {mdf(p, v, rt, 0, V);}
	pll get(ll lb, ll rb, ll x, ll lx, ll rx) {
		if (!x) return mkp(-1, inf);
		if (lb <= lx && rx <= rb) return mkp(fr[x], mn[x]);
		auto lq = get(lb, rb, l[x], lx, mid), rq = get(lb, rb, r[x], mid + 1, rx);
		if (lq.second <= rq.second) return lq;
		return rq;
	}
	pll get(ll l, ll r) {return get(l, r, rt, 0, V);}
} st;;

ll p[MAXN], w[MAXN], d, g, n;

pll slv(ll l, ll r, ll yl) {
	if (r - l + 1 <= yl - 1) return mkp(-1, 0);
	pll ch = st.get(l, r);
	pll lq = slv(l, ch.first - 1, yl), rq = slv(ch.first + 1, r, g);
	ll jy = r + 1 - ch.first - (lq.first == -1) * (yl - ch.first);
	return mkp(lq.first == -1 ? ch.first : lq.first, lq.second + jy * ch.second + rq.second);
}

vector<ll> wj = {0};

int main() {
	cin >> d >> g >> n;
	st.init(d);
	for (ll i = 1; i <= n; ++i) cin >> p[i] >> w[i], st.mdf(p[i], w[i]), wj.empb(p[i]);
	wj.empb(d);
	sort(wj.begin(), wj.end());
	for (ll i = 1; i < wj.size(); ++i) if (wj[i] - wj[i - 1] > g) puts("-1"), exit(0);
	cout << slv(0, d - 1, g).second << endl;
	return 0;
}

isn't this segment tree + divide and conquer $$$\mathcal O(m\log d)$$$

link

sidhu_sahab

442D - Adam and Tree

I hadn't mentioned the conclusion "brute force is $$$O(n\log n)$$$" at first. When i got the dp equation $$$\mathrm{dp}_x=\max(\mathrm{dp}_i,\mathrm{se}_x+1)$$$, where $$$i$$$ is a child of $$$x$$$, and $$$\mathrm{se}_x$$$ is the second maximum $$$\mathrm{dp}_i$$$, my first reaction is that the $$$\mathrm{dp}$$$-s updated in round $$$i$$$ is a path, started from $$$i$$$, and contained in the path $$$i$$$ to root. We can use a Link-Cut Tree (maybe without makeroot(x)? idk) to maintain that. But I don't know to maintain the following:

• $$$\max\mathrm{dp}_i,\mathrm{se}_x$$$
• $$$\mathrm{fr}_x$$$, which means where the $$$\max\mathrm{dp}_i$$$ is from
• $$$\mathrm{stp}_x$$$, which means "when $$$\mathrm{dp}_x$$$ is updated (by 1), where should the update stop

when pushing up and pushing down. After maintaining that, we can simply use a lazy tag to do the dp update. Can anybody help?

This is my solution for 2040E - Control of Randomness. It passed the tests, but I’m not sure whether deriving the DP formula in this way (splitting the min, solving the equation, and then putting the min back) is rigorous.

More formally, if we have $$$x_0$$$ is the only number that satisfies $$$x_0=f(x_0)$$$, and so do $$$x_1$$$ and $$$g(x_1)$$$, can we say that $$$x=h(f(x),g(x))\Leftrightarrow x=h(x_0,x_1)$$$? What if $$$h(x,y)=\min(x,y)$$$?

https://arxiv.org/pdf/2411.19826

Amazed by the perseverance, intellect, and exploratory spirit of mathematicians.