Submission #872861

#	Time	Username	Problem	Language	Result	Execution time	Memory
872861		MinaRagy06	Two Currencies (JOI23_currencies)	C++17	100 / 100	1766 ms	169384 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r) >> 1)

const int N = 100'005;
const ll inf = 1e18;
int anc[N][17], st[N], en[N], t;
ll h[N];
vector<array<int, 2>> adj[N];
array<ll, 2> a[N];
void dfs(int i, int par, ll d) {
	h[i] = d;
	anc[i][0] = par;
	for (int j = 1; j < 17; j++) {
		anc[i][j] = anc[anc[i][j - 1]][j - 1];
	}
	st[i] = t++;
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, d + w);
	}
	en[i] = t - 1;
}
int getlca(int u, int v) {
	if (st[u] > st[v]) swap(u, v);
	if (st[u] <= st[v] && en[v] <= en[u]) {
		return u;
	}
	for (int j = 16; j >= 0; j--) {
		if (!(st[anc[u][j]] <= st[v] && en[v] <= en[anc[u][j]])) {
			u = anc[u][j];
		}
	}
	return anc[u][0];
}
struct node {
	ll val = 0;
	int cnt = 0;
	node(int x) {
		val = x, cnt = 1;
	}
	node() {}
	node& operator+=(node y) {
		val += y.val;
		cnt += y.cnt;
		return *this;
	}
	friend node operator+(node x, node y) {
		return x += y;
	}
	node& operator-=(node y) {
		val -= y.val;
		cnt -= y.cnt;
		return *this;
	}
	friend node operator-(node x, node y) {
		return x -= y;
	}
	node& operator*=(int x) {
		val *= x;
		cnt *= x;
		return *this;
	}
	friend node operator*(int x, node y) {
		return y *= x;
	}
};
node lazy[1 << 18];
void upd(int i, int l, int r, int s, int e, node v) {
	if (s <= l && r <= e) {
		lazy[i] += v;
		return;
	}
	if (r < s || e < l) {
		return;
	}
	upd(i << 1, l, mid, s, e, v);
	upd(i << 1 | 1, mid + 1, r, s, e, v);
}
node get(int i, int l, int r, int x) {
	if (l == r) {
		return lazy[i];
	}
	if (x <= mid) {
		return get(i << 1, l, mid, x) + lazy[i];
	} else {
		return get(i << 1 | 1, mid + 1, r, x) + lazy[i];
	}
}
int n, m, q;
node height(int u) {
	return get(1, 0, t - 1, st[u]);
}
vector<array<ll, 7>> ask[2][N];
vector<array<ll, 5>> ansask[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	array<int, 3> edges[n - 1];
	for (int i = 0; i < n - 1; i++) {
		auto &[u, v, cnt] = edges[i];
		cin >> u >> v;
		cnt = 0;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i][1] >> a[i][0];
		a[i][1]--;
		edges[a[i][1]][2]++;
	}
	for (auto &[u, v, cnt] : edges) {
		adj[u].push_back({v, cnt});
		adj[v].push_back({u, cnt});
	}
	dfs(1, 1, 0);
	for (auto &[u, v, cnt] : edges) {
		if (st[u] > st[v]) {
			swap(u, v);
		}
	}
	sort(a, a + m);
	array<ll, 4> query[q];
	for (int i = 0; i < q; i++) {
		auto &[u, v, x, y] = query[i];
		cin >> u >> v >> y >> x;
		ask[0][m >> 1].push_back({u, v, x, y, 0, m, i});
	}
	int cur = 0;
	for (int _ = 0; _ < 17; _++) {
		bool done = 0;
		for (int i = 0; i < (1 << 18); i++) {
			lazy[i] = node();
		}
		for (int md = 0; md <= m; md++) {
			ask[cur ^ 1][md].clear();
		}
		int idx = -1;
		for (int md = 0; md <= m; md++) {
			if (md && idx + 1 < m) {
				ll tar = a[idx + 1][0];
				while (idx + 1 < m && a[idx + 1][0] == tar) {
					idx++;
					int e = a[idx][1];
					int v = edges[e][1];
					upd(1, 0, t - 1, st[v], en[v], a[idx][0]);
				}
			}
			for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) {
				done = 1;
				int lca = getlca(u, v);
				node ttl = height(u) + height(v) - 2 * height(lca);
				if (ttl.val <= x) {
					l = md + 1;
				} else {
					r = md - 1;
				}
				if (l <= r) {
					ask[cur ^ 1][(l + r) >> 1].push_back({u, v, x, y, l, r, qidx});
				} else {
					ansask[r].push_back({u, v, x, y, qidx});
				}
			}
		}
		if (!done) break;
		cur ^= 1;
	}
	ll ans[q];
	memset(ans, '?', sizeof ans);
	int idx = -1;
	for (int i = 0; i < (1 << 18); i++) {
		lazy[i] = node();
	}
	for (int i = 0; i <= m; i++) {
		if (i && idx + 1 < m) {
			ll tar = a[idx + 1][0];
			while (idx + 1 < m && a[idx + 1][0] == tar) {
				idx++;
				int e = a[idx][1];
				int v = edges[e][1];
				upd(1, 0, t - 1, st[v], en[v], a[idx][0]);
			}
		}
		for (auto &[u, v, x, y, qidx] : ansask[i]) {
			int lca = getlca(u, v);
			node ttl = height(u) + height(v) - 2 * height(lca);
			ll dist = h[u] + h[v] - 2 * h[lca];
			x -= ttl.val;
			dist -= ttl.cnt;
			ll nxt = inf;
			if (idx + 1 < m) {
				nxt = a[idx + 1][0];
			}
			ll rem = min((ll)dist, x / nxt);
			dist -= rem;
			y -= dist;
			ans[qidx] = y;
		}
	}
	for (int i = 0; i < q; i++) {
		if (ans[i] < 0) {
			cout << "-1\n";
		} else {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

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