Submission #791986

#	Time	Username	Problem	Language	Result	Execution time	Memory
791986		TranGiaHuy1508	Two Currencies (JOI23_currencies)	C++17	100 / 100	1573 ms	116128 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

using ii = pair<int, int>;

struct Segtree{
	vector<int> tree;
	int _n;

	Segtree() = default;
	Segtree(int N): tree(4*N), _n(N) {}

	int get(int pos) { return get(1, 0, _n - 1, pos); }
	int get(int i, int l, int r, int pos){
		if (l == pos && r == pos) return tree[i];
		int mid = (l + r) >> 1;
		if (pos <= mid) return tree[i] + get(i<<1, l, mid, pos);
		else return tree[i] + get(i<<1|1, mid+1, r, pos);
	}

	void update(int tl, int tr, int delta) { update(1, 0, _n - 1, tl, tr, delta); }
	void update(int i, int l, int r, int tl, int tr, int delta){
		if (tl <= l && r <= tr) tree[i] += delta;
		else if (tl > r || tr < l) return;
		else{
			int mid = (l + r) >> 1;
			update(i<<1, l, mid, tl, tr, delta);
			update(i<<1|1, mid+1, r, tl, tr, delta);
		}
	}
};

template <class T>
struct RMQ{
	vector<vector<T>> table;
	int _n, _lg;

	RMQ() = default;
	RMQ(vector<T> &V){
		_n = V.size();
		_lg = 64 - __builtin_clzll(_n);

		table.assign(_lg, vector<T>(_n));
		table[0] = V;

		for (int j = 1; j < _lg; j++){
			for (int i = 0; i + (1 << j) <= _n; i++){
				table[j][i] = min(table[j-1][i], table[j-1][i + (1 << (j-1))]);
			}
		}
	}

	T get(int l, int r){
		if (l > r) swap(l, r);
		int j = 63 - __builtin_clzll(r - l + 1);
		return min(table[j][l], table[j][r - (1 << j) + 1]);
	}
};

struct Query{
	int a, b;
	int lca;
	int gold, silver;

	int idx;
};

struct PBS{
	int lb, rb;
	vector<Query> qs;
};

int n, m, q;
vector<vector<int>> adj;
vector<ii> edges;
vector<ii> checkpoints;
vector<Query> all_queries;

int timer = 0;
vector<int> tin, tout, occ;
vector<ii> eulertour;
RMQ<ii> rmq;

vector<int> max_silver;

void dfs_euler(int x, int p = -1, int d = 0){
	tin[x] = timer++;
	occ[x] = eulertour.size();
	eulertour.emplace_back(d, x);

	for (auto k: adj[x]){
		if (k == p) continue;
		dfs_euler(k, x, d+1);
		eulertour.emplace_back(d, x);
	}

	tout[x] = timer - 1;
}

inline int LCA(int x, int y){
	return rmq.get(occ[x], occ[y]).second;
}

void main_program(){
	cin >> n >> m >> q;

	adj.resize(n);
	edges.resize(n-1);
	checkpoints.resize(m);
	all_queries.resize(q);

	tin.resize(n);
	tout.resize(n);
	occ.resize(n);
	max_silver.resize(q);

	for (int i = 0; i < n-1; i++){
		int x, y; cin >> x >> y;
		x--; y--;

		adj[x].push_back(y);
		adj[y].push_back(x);

		edges[i] = {x, y};
	}

	for (int i = 0; i < m; i++){
		int P, cost; cin >> P >> cost;
		P--;

		checkpoints[i] = {P, cost};
	}

	sort(checkpoints.begin(), checkpoints.end(), [](ii A, ii B){
		return A.second < B.second;
	});

	dfs_euler(0);
	rmq = RMQ<ii>(eulertour);

	for (int i = 0; i < n-1; i++){
		if (tin[edges[i].first] > tin[edges[i].second])
			swap(edges[i].first, edges[i].second);
	}

	for (int i = 0; i < q; i++){
		int a, b, gold, silver;
		cin >> a >> b >> gold >> silver;
		a--; b--;
		int lca = LCA(a, b);

		all_queries[i] = Query{a, b, lca, gold, silver, i};
	}

	vector<PBS> crrpbs = {PBS{0, m, all_queries}};
	while (!crrpbs.empty()){
		vector<PBS> nxtpbs;
		int prev = -1;
		Segtree st(n);
		Segtree stcnt(n);
		for (auto range: crrpbs){
			if (range.lb == range.rb){
				for (int i = prev + 1; i < range.lb; i++){
					auto [P, cost] = checkpoints[i];
					int x = edges[P].second;
					st.update(tin[x], tout[x], cost);
					stcnt.update(tin[x], tout[x], 1);
				}
				prev = max(prev, range.lb - 1);

				for (auto query: range.qs){
					max_silver[query.idx] =
					stcnt.get(tin[query.a]) + stcnt.get(tin[query.b]) - stcnt.get(tin[query.lca]) * 2;
				}
				continue;
			}

			int mid = (range.lb + range.rb) >> 1;
			for (int i = prev + 1; i <= mid; i++){
				auto [P, cost] = checkpoints[i];
				int x = edges[P].second;
				st.update(tin[x], tout[x], cost);
				stcnt.update(tin[x], tout[x], 1);
			}
			prev = max(prev, mid);

			PBS leftnode{range.lb, mid, {}}, rightnode{mid+1, range.rb, {}};
			for (auto query: range.qs){
				int silver_cost = st.get(tin[query.a]) + st.get(tin[query.b]) - st.get(tin[query.lca]) * 2;
				if (silver_cost <= query.silver) rightnode.qs.push_back(query);
				else leftnode.qs.push_back(query);
			}

			if (!leftnode.qs.empty()) nxtpbs.push_back(leftnode);
			if (!rightnode.qs.empty()) nxtpbs.push_back(rightnode);
		}
		crrpbs.swap(nxtpbs);
	}

	Segtree st(n);
	for (auto pt: checkpoints){
		int x = edges[pt.first].second;
		st.update(tin[x], tout[x], 1);
	}

	for (int i = 0; i < q; i++){
		auto query = all_queries[i];
		int cnt_pt = st.get(tin[query.a]) + st.get(tin[query.b]) - st.get(tin[query.lca]) * 2;
		int gold_cost = cnt_pt - max_silver[i];
		if (gold_cost > query.gold) cout << "-1\n";
		else cout << query.gold - gold_cost << "\n";
	}
}

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