Submission #918445

#	Time	Username	Problem	Language	Result	Execution time	Memory
918445		OAleksa	Two Currencies (JOI23_currencies)	C++14	100 / 100	3713 ms	161716 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int C = 1e9 + 69;
const int K = 18;
const int inf = 1e18;
int up[N][K];
int n, m, q, p[N], c[N], par[N], timer, tin[N], tout[N];
int root[N], lc[30 * N], rc[30 * N], node, vis[N];
int st[30 * N], cnt[30 * N];
vector<int> g[N];
vector<pair<int, int>> e;
map<pair<int, int>, vector<int>> edges;
void Modify(int v, int rt, int tl, int tr, int p) {
	if (tl == tr) {
		cnt[v] = cnt[rt] + 1;
		st[v] = st[rt] + tl;
	}
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid) {
			lc[v] = ++node;
			rc[v] = rc[rt];
			Modify(lc[v], lc[rt], tl, mid, p);
		}
		else {
			rc[v] = ++node;
			lc[v] = lc[rt];
			Modify(rc[v], rc[rt], mid + 1, tr, p);
		}
		st[v] = st[lc[v]] + st[rc[v]];
		cnt[v] = cnt[lc[v]] + cnt[rc[v]];
	}
}
int GetSum(int v, int v1, int v2, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v] + st[v1] - 2 * st[v2];
	else {
		int mid = (tl + tr) / 2;
		return GetSum(lc[v], lc[v1], lc[v2], tl, mid, l, r) + GetSum(rc[v], rc[v1], rc[v2], mid + 1, tr, l, r);
	}
}
int GetCnt(int v, int v1, int v2, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return cnt[v] + cnt[v1] - 2 * cnt[v2];
	else {
		int mid = (tl + tr) / 2;
		return GetCnt(lc[v], lc[v1], lc[v2], tl, mid, l, r) + GetCnt(rc[v], rc[v1], rc[v2], mid + 1, tr, l, r);
	}
}
int Cnt(int v, int tl, int tr, int p) {
	if (tl == tr)
		return cnt[v];
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			return Cnt(lc[v], tl, mid, p);
		else
			return Cnt(rc[v], mid + 1, tr, p);
	}
}
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	par[v] = p;
	tin[v] = ++timer;
	up[v][0] = p;
	root[v] = root[p];
	int x = v, y = p;
	if (x > y)
		swap(x, y);
	if (edges.count({x, y})) {
		for (auto u : edges[{x, y}]) {
			int nr = ++node;
			Modify(nr, root[v], 0, C, u);
			root[v] = nr;
		}
	}
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> m >> q;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  		e.push_back({a, b});
  	}
  	for (int i = 1;i <= m;i++) {
  		int p, x;
  		cin >> p >> x;
  		vis[p] = 1;
  		--p;
  		int a, b;
  		tie(a, b) = e[p];
  		if (a > b)
  			swap(a, b);
  		edges[{a, b}].push_back(x);
  	}
  	dfs(1, 0);
  	while (q--) {
  		int s, t, x, y;
  		cin >> s >> t >> x >> y;
  		int lc = lca(s, t);
  		int l = 0, r = C, ans = -1;
  		int uk = cnt[root[s]] + cnt[root[t]] - 2 * cnt[root[lc]];
  		auto Check = [&](int mid) {
  			int sum = GetSum(root[s], root[t], root[lc], 0, C, 0, mid);
  			int c = GetCnt(root[s], root[t], root[lc], 0, C, 0, mid);
  			return make_pair(sum, c);
  		};
  		while (l <= r) {
  			int mid = (l + r) / 2;
  			auto p = Check(mid);
  			if (p.f > y) {
  				int x = Cnt(root[s], 0, C, mid) + Cnt(root[t], 0, C, mid);
  				x -= 2 * Cnt(root[lc], 0, C, mid);
  				if (p.f - (x - 1) * mid <= y) {
  					int r = y - (p.f - x * mid);
  					p.s -= x;
  					p.s += r / mid;
  					p.f -= x * mid;
  					p.f += r / mid * mid;
  				}
  			}
  			if (p.f <= y) {
  				ans = p.s;
  				l = mid + 1;
  			} 
  			else
  				r = mid - 1;
  		}
  		if (uk - ans <= x)
  			ans = x - (uk - ans);
  		else
  			ans = -1;
  		cout << ans << '\n';
  	}
	}
  return 0;
}

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