Submission #892062

#	Time	Username	Problem	Language	Result	Execution time	Memory
892062		iskhakkutbilim	Two Currencies (JOI23_currencies)	C++17	100 / 100	644 ms	66244 KiB

currencies

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

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;



struct Fenwick{
	int n;
	vector<int> fenw;
	Fenwick(int sz){
		n = sz;
		fenw.resize(n+1, 0);
	};
	
	void add(int i, int x){
		for(; i <= n; i+= i&-i){
			fenw[i]+= x;
		}
	}
	
	int pref(int i){
		int s = 0;
		for(; i > 0; i-= i & -i){
			s+= fenw[i];
		}
		return s;
	}
	int sum(int l, int r){
		return pref(r) - pref(l-1);
	}
};
int n, m, q;
vector<int > g[N+10];
vector< pair<int, int> > edge;
int depth[N+10], up[N+10][20], sum[N+10][20];
int tin[N+10], tout[N+10], timer = 1;
void dfs(int v, int par){
	tin[v] = timer++;
	up[v][0] = par;
	for(int to : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		dfs(to, v);
	}
	tout[v] = timer - 1;
}
int lca(int a, int b){
	if(depth[b] < depth[a]) swap(a, b);
	int k = depth[b] - depth[a];
	for(int i = 0;i < 20; i++){
		if(k & (1<<i)) b = up[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i--){
		if(up[b][i] != up[a][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}


int ones(int a, int d){
	int s = 0;
	for(int i = 0;i < 20; i++){
		if(d & (1<<i)){
			s+= sum[a][i];
			a = up[a][i];
		}
	}
	return s;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		edge.push_back({a, b});
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	vector<array<int, 2> > adds;
	for(int i = 0;i < m; i++){
		int p, c; cin >> p >> c;
		int a = edge[p-1].ff, b = edge[p-1].ss;
		if(depth[a] < depth[b]) swap(a, b);
		adds.push_back({a, c});
		sum[a][0]+= 1;
	}
	sort(all(adds), [&](auto A, auto B){
		return A[1] < B[1];
	});
	for(int j = 1;j < 20; j++){
		for(int i = 1;i <= n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1];
		}
	}
	vector<array<int, 4> > query(q);
	vector<int> overall, lc;
	vector< array<int, 2> > rn(q, {0, m+1});
	for(auto &A : query){
		cin >> A[0] >> A[1] >> A[2] >> A[3];
		int all_p = lca(A[0], A[1]);
		lc.push_back(all_p);
		int checkpoints = ones(A[0],  depth[A[0]] - depth[lc.back()]) + ones(A[1], depth[A[1]] - depth[lc.back()]);
		overall.push_back(checkpoints);
	}
	vector<int> ans(q);
	for(int i = 0;i < q; i++){
		auto A = query[i];
		ans[i] = A[2] - overall[i];
	}
	
	while(true){
		Fenwick f1(n + 2), f2(n + 2);
		vector< vector<int> > middles(m + 1);
		bool finish = true;
		for(int i = 0;i < q; i++){
			if(rn[i][0] + 1 < rn[i][1]){
				int mid = (rn[i][0] + rn[i][1]) / 2;
				middles[mid].push_back(i);
				finish = false;
			}
		}
		
		for(int i = 0;i <= m; i++){
			
			for(auto idx : middles[i]){
				auto [s, t, gold, silver]  =  query[idx];
				int LC = lc[idx], checkpoints = overall[idx]; 
				int sum = f1.pref(tin[s]) + f1.pref(tin[t]) - 2 * f1.pref(tin[LC]);
				int cnt = f2.pref(tin[s]) + f2.pref(tin[t]) - 2 * f2.pref(tin[LC]);
				checkpoints-= cnt;
				if(sum <= silver){
					ans[idx] =  max(ans[idx], gold - checkpoints);
					rn[idx][0] = i;
				}else{
					rn[idx][1] = i;
				}
			}
			if(i < m){
				auto [a, c] = adds[i];
				f1.add(tin[a], c);
				f1.add(tout[a] + 1, -c);
				f2.add(tin[a], 1);
				f2.add(tout[a] + 1, -1);
			}
			
		}
		if(finish) break;
	}
	
	for(int i = 0;i < q; i++) cout << max(-1LL, ans[i]) << '\n';
	
	
	return 0;
}

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