Submission #1298829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298829		Jawad_Akbar_JJ	Two Currencies (JOI23_currencies)	C++20	0 / 100	9 ms	3220 KiB

currencies

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1<<17, K = 320, B = 320;
vector<pair<int,int>> nei[N];
vector<int> vec[N], adj[N];
vector<pair<int, pair<int, int>>> ord;
long long inf = 2e18, arr[N], Sum[N], y[N];
int blk[N], st[N], en[N], s[N], t[N], x[N], cr0, cr1, cr2 = 1, Cnt;
int cnt1[N], cnt2[N], num[N], seen[N], Ans[N], ind[N], dv[N], lv[N], Par[N][20], hei[N];

void block(vector<int> me){
	++cr1;
	for (int j : me)
		blk[j] = cr1;
}

void dfs0(int u, int p){
	for (auto [i, id] : nei[u]){
		if (i == p)
			continue;
		lv[i] = lv[u];
		for (int j : vec[id]){
			// cout<<lv[i]<<"    "<<cr2 + 1<<endl;
			adj[lv[i]].push_back(++cr2);
			num[cr2] = j;
			lv[i] = cr2;
		}
		dfs0(i, u);
	}
}

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

	st[u] = ++cr0;
	vector<int> me;
	for (int i : adj[u]){
		vector<int> nw = dfs(i, u);
		me.insert(me.end(), nw.begin(), nw.end());
		if (me.size() >= K)
			block(me), me = {};
	}
	en[u] = ++cr0;
	me.push_back(u);
	return me;
}

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

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

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

void toggle(int id){
	if (num[id] == 0)
		return;
	int cur = ind[id], d = dv[cur];

	if (seen[id]){
		Cnt--;
		cnt1[cur]--;
		cnt2[d]--;
		Sum[d] -= num[id];
	}
	else{
		Cnt++;
		cnt1[cur]++;
		cnt2[d]++;
		Sum[d] += num[id];
	}
	seen[id] ^= 1;
}

void moveLR(int u, int v){
	// cout<<u<<" "<<v<<endl;
	while (st[u] > st[v] or en[u] < en[v]){
		toggle(u);
		u = Par[u][0];
	}
	// cout<<u<<" "<<v<<endl;
	while (v != u){
		toggle(v);
		v = Par[v][0];
	}
	// cout<<"done"<<endl;
}

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);
		arr[i-1] = c;
	}

	sort(arr, arr + m);
	m = unique(arr, arr + m) - arr;
	for (int i=m;i<N;i++)
		arr[i] = inf;

	lv[1] = 1;
	dfs0(1, 0);
	block(dfs(1, 0));

	for (int i=1;i<N;i++)
		ind[i] = upper_bound(arr, arr + N, num[i] - 1) - arr, dv[i] = i / B;

	for (int i=1;i<=q;i++){
		cin>>s[i]>>t[i]>>x[i]>>y[i];
		s[i] = lv[s[i]], t[i] = lv[t[i]];
		ord.push_back({blk[s[i]], {t[i], i}});
	}

	// cout<<"done"<<endl;
	// return 0;

	sort(ord.begin(), ord.end());

	int L = 1, R = 1;
	for (auto [vl, pr] : ord){
		int id = pr.second, cur = -1, d = -1, gld;
		// cout<<id<<endl;
		moveLR(L, s[id]);
		moveLR(R, t[id]);
		int lca = LCA(s[id], t[id]);
		toggle(lca);
		L = s[id], R = t[id], gld = Cnt;
			
		// cout<<id<<endl;
		while (arr[cur + B] != inf and y[id] >= Sum[d + 1])
			d++, cur += B, y[id] -= Sum[d], gld -= cnt2[d];
		while (arr[cur+1] != inf and arr[cur + 1] * cnt1[cur + 1] <= y[id])
			cur++, y[id] -= arr[cur] * cnt1[cur], gld -= cnt1[cur];

		Ans[id] = max(-1LL, x[id] - gld + y[id] / arr[++cur]);
		toggle(lca);
	}

	for (int i=1;i<=q;i++)
		cout<<Ans[i]<<' ';
	cout<<'\n';

}

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