Submission #1213273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213273		k1r1t0	Two Currencies (JOI23_currencies)	C++20	100 / 100	432 ms	57612 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 110000;
const int LOGN = 20;

struct edge {int u, v;};
struct ch {int v, c;};
struct route {int s, t, lca, x, y, lans, rans, id;};

struct fenwick {
	vector<int> ff; int n;
	fenwick() {}
	fenwick(int n) {
		this->n = n;
		ff = vector<int>(n + 1, 0);
	}
	void upd(int k, int x) {
		for (; k <= n; k += k & -k)
			ff[k] += x;
	}
	int get(int k) {
		int ans = 0;
		for (; k >= 1; k -= k & -k)
			ans += ff[k];
		return ans;
	}
};

int n, m, q, dd[N], jj[N][LOGN], tin[N], tout[N], tcur = 0, ans[N];
edge ee[N];
ch cc[N];
vector<route> rr;
vector<int> g[N];
fenwick cnt;

void dfs(int v, int p = -1) {
	dd[v] = (p == -1 ? 0 : dd[p] + 1);
	jj[v][0] = (p == -1 ? v : p);
	for (int k = 1; k < LOGN; k++)
		jj[v][k] = jj[jj[v][k - 1]][k - 1];
	tin[v] = ++tcur;
	for (int u : g[v]) if (u != p)
		dfs(u, v);
	tout[v] = tcur;
}

int lca(int u, int v) {
	if (dd[u] < dd[v])
		swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if (dd[u] - (1 << k) >= dd[v])
			u = jj[u][k];
	if (u == v) return u;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jj[u][k] != jj[v][k]) {
			u = jj[u][k];
			v = jj[v][k];
		}
	return jj[u][0];
}

void upd(int v, int c) {
	cnt.upd(tin[v], c);
	if (tout[v] < n)
		cnt.upd(tout[v] + 1, -c);
}

int sum(route rt) {
	return cnt.get(tin[rt.s]) + cnt.get(tin[rt.t]) - 2 * cnt.get(tin[rt.lca]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++) {
		cin >> ee[i].u >> ee[i].v;
		g[ee[i].u].push_back(ee[i].v);
		g[ee[i].v].push_back(ee[i].u);
	}
	for (int i = 1; i <= m; i++)
		cin >> cc[i].v >> cc[i].c;
	rr = vector<route>(q);
	for (int i = 0; i < q; i++)
		cin >> rr[i].s >> rr[i].t >> rr[i].x >> rr[i].y;
	dfs(1);
	for (int i = 1; i <= m; i++) {
		int u = ee[cc[i].v].u;
		int v = ee[cc[i].v].v;
		if (dd[u] < dd[v])
			cc[i].v = v;
		else
			cc[i].v = u;
	}
	sort(cc + 1, cc + m + 1, [&](auto c1, auto c2) {return c1.c < c2.c;});
	for (int i = 0; i < q; i++) {
		rr[i].id = i + 1;
		rr[i].lans = 0;
		rr[i].rans = m;
		rr[i].lca = lca(rr[i].s, rr[i].t);
	}
	while (true) {
		bool good = true;
		vector<route> nr, cur;
		int ptr = 1;
		cnt = fenwick(n);
		for (int i = 0; i < q; i++) {
			cur.push_back(rr[i]);
			if (i == q - 1 || rr[i].lans != rr[i + 1].lans) {
				int tl = rr[i].lans;
				int tr = rr[i].rans;
				if (tl == tr) {
					for (auto &rt : cur)
						nr.push_back(rt);
				} else {
					int mid = (tl + tr) / 2 + 1;
					while (ptr <= mid) {
						upd(cc[ptr].v, cc[ptr].c);
						ptr++;
					}
					for (auto &rt : cur)
						rt.lans = sum(rt);
					for (auto rt : cur)
						if (rt.y < rt.lans) {
							rt.lans = tl;
							rt.rans = mid - 1;
							if (tl != mid - 1) good = false;
							nr.push_back(rt);
						}
					for (auto rt : cur)
						if (rt.y >= rt.lans) {
							rt.lans = mid;
							rt.rans = tr;
							if (mid != tr) good = false;
							nr.push_back(rt);
						}
				}
				cur.clear();
			}
		}
		rr = nr;
		if (good) break;
	}
	cnt = fenwick(n);
	int ptr = m;
	for (int i = q - 1; i >= 0; i--) {
		while (ptr > rr[i].lans) {
			upd(cc[ptr].v, 1);
			ptr--;
		}
		rr[i].x -= sum(rr[i]);
	}
	for (auto rt : rr)
		ans[rt.id] = max(rt.x, -1ll);
	for (int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32