Submission #1083760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083760		hahahaha	Two Currencies (JOI23_currencies)	C++17	100 / 100	483 ms	45236 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Fenwick {
	vector<T> f;
	Fenwick(int N = 0): f(N) {
	}

	void add(int x, T v) {
		for (; x < int(f.size()); x |= (x + 1)) f[x] += v;
	}

	T get(int x) {
		T ans{};
		for (; x >= 0; x = (x & (x + 1)) - 1) ans += f[x];
		return ans;
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int N, M, Q; cin >> N >> M >> Q;
	vector<vector<int>> adj(N);
	vector<array<int, 2>> E(N - 1);
	for (int i = 0; i + 1 < N; ++i) {
		cin >> E[i][0] >> E[i][1]; --E[i][0], --E[i][1];
		adj[E[i][0]].push_back(E[i][1]);
		adj[E[i][1]].push_back(E[i][0]);
	}

	vector<int> par(N, -1);
	vector<int> sz(N);
	vector<int> depth(N);
	function<void(int)> dfs = [&](int v) {
		sz[v] = 1;
		for (int u : adj[v]) {
			par[u] = v;
			adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
			depth[u] = depth[v] + 1;
			dfs(u);
			sz[v] += sz[u];
		}
	};

	dfs(0);
	int timer = 0;
	vector<int> top(N);
	vector<int> tin(N);
	vector<int> tout(N);
	function<void(int, int)> hld = [&](int v, int t) {
		tin[v] = timer++;
		top[v] = t;
		int nv = -1;
		for (int u : adj[v]) {
			if (nv == -1 || sz[u] > sz[nv]) nv = u;
		}

		if (nv >= 0) hld(nv, t);
		for (int u : adj[v]) {
			if (u != nv) hld(u, u);
		}
		tout[v] = timer;
	};

	hld(0, 0);
	auto get_lca = [&](int v, int u) {
		while (top[v] != top[u]) {
			if (depth[top[v]] > depth[top[u]]) {
				v = par[top[v]];
			} else {
				u = par[top[u]];
			}
		}
		return depth[v] <= depth[u] ? v : u;
	};

	for (int i = 0; i < N - 1; ++i) {
		if (depth[E[i][0]] > depth[E[i][1]]) {
			swap(E[i][0], E[i][1]);
		}
	}
	vector<pair<int, int>> cpts(M);
	for (int i = 0; i < M; ++i) {
		int k, c; cin >> k >> c;
		cpts[i] = {c, E[k - 1][1]};
	}

	sort(cpts.begin(), cpts.end());
	Fenwick<int> f(N);
	for (auto [c, v] : cpts) {
		f.add(tin[v], +1);
		f.add(tout[v], -1);
	}

	vector<int> from(Q);
	vector<int> to(Q);
	vector<int> lca(Q);
	vector<int> cnt(Q);
	vector<int> gold(Q);
	vector<int> ans(Q);
	vector<int64_t> silver(Q);
	vector<int> lo(Q, 0);
	vector<int> hi(Q, M - 1);

	for (int q = 0; q < Q; ++q) {
		cin >> from[q] >> to[q]; --from[q], --to[q];
		lca[q] = get_lca(from[q], to[q]);
		cnt[q] = f.get(tin[from[q]]) + f.get(tin[to[q]]) - 2 * f.get(tin[lca[q]]);
		cin >> gold[q] >> silver[q];
		ans[q] = gold[q] - cnt[q];
	}

	vector<vector<int>> queries(M);
	while (true) {
		bool done = true;
		for (int q = 0; q < Q; ++q) if (lo[q] <= hi[q]) {
			done = false;
			int md = (lo[q] + hi[q]) / 2;
			queries[md].push_back(q);
		}

		if (done) break;
		Fenwick<int> fcnt(N);
		Fenwick<int64_t> fsum(N);
		for (int md = 0; md < M; ++md) {
			auto [c, v] = cpts[md];
			fcnt.add(tin[v], +1);
			fcnt.add(tout[v], -1);
			fsum.add(tin[v], +c);
			fsum.add(tout[v], -c);

			for (int q : queries[md]) {
				int64_t sum = fsum.get(tin[from[q]]) + fsum.get(tin[to[q]]) - 2 * fsum.get(tin[lca[q]]);
				int cnt0 = fcnt.get(tin[from[q]]) + fcnt.get(tin[to[q]]) - 2 * fcnt.get(tin[lca[q]]);
				if (sum <= silver[q]) {
					lo[q] = md+1;
					ans[q] = gold[q] - (cnt[q] - cnt0);
				} else {
					hi[q] = md-1;
				}
			}
		}
		for (int i = 0; i < M; ++i) queries[i].clear();
	}

	for (int q = 0; q < Q; ++q) {
		cout << max(ans[q], -1) << '\n';
	}
	return 0;
}

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