Submission #1298576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298576		Jawad_Akbar_JJ	Two Currencies (JOI23_currencies)	C++20	100 / 100	1311 ms	153952 KiB

currencies

#include <iostream>
#include <vector>
#include <map>

using namespace std;
#define int long long
const int N = (1<<17) + 1;
vector<pair<int, int>> nei[N];
vector<int> vec[N];
int Par[N][20], hei[N], inv[N], cur;
map<int, int> mp, mp2;
struct node{
	node *lc, *rc;
	int cnt = 0, sum = 0;
} *seg[N<<1];

node* insert(node* cur, int t, int i, int v, int st = 1, int en = N){
	if (i >= en or i < st)
		return cur;
	node* nw = new node();
	if (en - st == 1){
		nw->cnt = cur->cnt + t;
		nw->sum = cur->sum + t * v;
		return nw;
	}

	int mid = (st + en) / 2;
	nw->lc = insert(cur->lc, t, i, v, st, mid);
	nw->rc = insert(cur->rc, t, i, v, mid, en);
	nw->sum = nw->lc->sum + nw->rc->sum;
	nw->cnt = nw->lc->cnt + nw->rc->cnt;
	return nw;
}

int get(node *cur, int k, int st = 1, int en = N){
	if (k == 0)
		return 0;
	if (en - st == 1)
		return cur->sum;
	int mid = (st + en) / 2;
	if (k < mid)
		return get(cur->lc, k, st, mid);
	return get(cur->rc, k, mid, en) + cur->lc->sum;
}

int getCnt(node *cur, int k, int st = 1, int en = N){
	if (k == 0)
		return 0;
	if (en - st == 1)
		return cur->cnt;
	int mid = (st + en) / 2;
	if (k < mid)
		return getCnt(cur->lc, k, st, mid);
	return getCnt(cur->rc, k, mid, en) + cur->lc->cnt;
}

node* build(int n){
	// cout<<n<<endl;
	node *nw = new node();
	if (n == 1)
		return nw;
	nw->lc = build(n / 2);
	nw->rc = build(n / 2);
	return nw;
}

void dfs(int u, int p){
	Par[u][0] = p;
	hei[u] = hei[p] + 1;
	for (int i=0;i<17;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (auto [i, id] : nei[u]){
		if (i == p)
			continue;
		seg[i] = insert(seg[u], 1, 0, 0);
		for (int j : vec[id])
			seg[i] = insert(seg[i], 1, mp2[j], j);
		dfs(i, u);
	}
}

int LCA(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);

	for (int i=17; i+1; i--){
		if ((1<<i) + hei[u] <= hei[v])
			v = Par[v][i];
	}

	for (int i=17; i+1; i--){
		if (Par[u][i] != Par[v][i])
			u = Par[u][i], v = Par[v][i];
	}
	return (u == v ? u : Par[v][0]);
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, q;
	cin>>n>>m>>q;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back({b, i});
		nei[b].push_back({a, i});
	}

	for (int i=1, p, c;i<=m;i++){
		cin>>p>>c;
		vec[p].push_back(c);
		mp[c];
	}

	for (auto [i, j] : mp)
		mp2[i] = ++cur, inv[cur] = i;

	// cout<<"done"<<endl;

	seg[1] = build(N);
	dfs(1, 0);

	// return 0;

	inv[cur + 1] = 1e18;
	for (int i=1;i<=q;i++){
		int s, t, x, y;
		cin>>s>>t>>x>>y;
		int lca = LCA(s, t);

		int l = 0, r = cur + 1;
		while (l + 1 < r){
			int mid = (l + r) / 2, k = get(seg[s], mid) + get(seg[t], mid) - 2 * get(seg[lca], mid);
			// cout<<mid<<" "<<get(seg[s], mid)<<" "<<get(seg[t], mid)<<" "<<get(seg[lca], mid)<<endl;
			if (k <= y)
				l = mid;
			else
				r = mid;
		}

		// cout<<s<<" "<<t<<" "<<lca<<endl;

		int c1 = seg[s]->cnt + seg[t]->cnt - 2 * seg[lca]->cnt;
		int c2 = getCnt(seg[s], r) + getCnt(seg[t], r) - 2 * getCnt(seg[lca], r);
		int c3 = getCnt(seg[s], r-1) + getCnt(seg[t], r-1) - 2 * getCnt(seg[lca], r-1);
		// cout<<"done"<<endl;
		c1 -= c2;
		c2 -= c3;

		y -= get(seg[s], l) + get(seg[t], l) - 2 * get(seg[lca], l);
		// cout<<"done"<<endl;
		// cout<<l<<" "<<r<<" "<<inv[r]<<" "<<y<<endl;
		c2 -= min(c2, y / inv[r]);

		// cout<<"done"<<endl;

		if (x < c1 + c2)
			cout<<-1<<'\n';
		else
			cout<<x - c1 - c2<<'\n';
	}
}

/*

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

*/

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