Submission #986508

#	Time	Username	Problem	Language	Result	Execution time	Memory
986508		vjudge3	Two Currencies (JOI23_currencies)	C++17	100 / 100	2380 ms	126404 KiB

currencies

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

int tin[100005], tout[100005], lift[100005][20], timer;
vector<int> g[100005];

struct Edge {
	int u, v;
} e[100005];

void dfs (int u, int p) {
	tin[u] = ++timer;
	lift[u][0] = p;
	for (int i = 1; i < 20; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
	for (auto& v : g[u]) if (v != p) dfs(v, u);
	tout[u] = ++timer;
}

bool anc (int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca (int u, int v) {
	if (anc(u, v)) return u;
	for (int i = 19; i >= 0; i--) if (lift[u][i] && !anc(lift[u][i], v)) u = lift[u][i];
	return lift[u][0];
}

int roots[200005], ver, k;
struct Node {
	ll cost;
	int ckpt, l, r;
} seg[8000005];

int build (int l, int r) {
	int t = ++k;
	if (l == r) return t;
	int mid = (l+r)/2;
	seg[t].l = build(l, mid);
	seg[t].r = build(mid+1, r);
	return t;
}

int upd (int id, int l, int r, int pos, ll cost, int cnt) {
	int t = ++k;
	seg[t] = seg[id];
	if (l == r) {
		seg[t].cost += cost;
		seg[t].ckpt += cnt;
		return t;
	}
	int mid = (l+r)/2;
	if (pos > mid) seg[t].r = upd(seg[id].r, mid+1, r, pos, cost, cnt);
	else seg[t].l = upd(seg[id].l, l, mid, pos, cost, cnt);
	seg[t].cost = seg[seg[t].l].cost + seg[seg[t].r].cost;
	seg[t].ckpt = seg[seg[t].l].ckpt + seg[seg[t].r].ckpt;
	return t;
}

auto operator+ (const pair<ll, int>& x, const pair<ll, int>& y) {return make_pair(x.first+y.first, x.second+y.second);}

pair<ll, int> query (int id, int l, int r, int ql, int qr) {
	if (qr < l || r < ql) return {0, 0};
	if (ql <= l && r <= qr) return {seg[id].cost, seg[id].ckpt};
	int mid = (l+r)/2;
	return query(seg[id].l, l, mid, ql, qr) + query(seg[id].r, mid+1, r, ql, qr);
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		e[i] = {u, v};
	}
	dfs(1, 0);
	vector<pair<ll, int>> ckpt;
	for (int i = 0; i < m; i++) {
		int p, c;
		cin >> p >> c;
		int u = e[p].u;
		if (tin[e[p].u] < tin[e[p].v]) u = e[p].v;
		ckpt.push_back({c, u});
	}
	sort(ckpt.begin(), ckpt.end());
	roots[++ver] = build(1, n*2);
	for (auto& [c, u] : ckpt) {
		ver++;
		roots[ver] = upd(roots[ver-1], 1, n*2, tin[u], c, 1);
		roots[ver] = upd(roots[ver], 1, n*2, tout[u], -c, -1);
	}
	while (q--) {
		int s, t;
		ll x, y;
		cin >> s >> t >> x >> y;
		int u = lca(s, t);
		int l = 1, r = m+2, best = 0;
		while (l+1 < r) {
			int mid = (l+r)/2;
			auto p1 = u == s ? make_pair(0LL, 0) : query(roots[mid], 1, n*2, tin[u]+1, tin[s]);
			auto p2 = u == t ? make_pair(0LL, 0) : query(roots[mid], 1, n*2, tin[u]+1, tin[t]);
			if (p1.first + p2.first <= y) {
				l = mid;
				best = max(best, p1.second + p2.second);
			} else r = mid;
		}
		int edges = query(roots[m+1], 1, n*2, tin[u]+1, tin[s]).second + query(roots[m+1], 1, n*2, tin[u]+1, tin[t]).second;
		int used = edges - best;
		if (used <= x) cout << x-used << '\n';
		else cout << "-1\n";
	}
	return 0;
}

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