Submission #976943

#	Time	Username	Problem	Language	Result	Execution time	Memory
976943		TomkeMonke	Two Currencies (JOI23_currencies)	C++17	100 / 100	1216 ms	67016 KiB

currencies

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
 
 
const int MAXN = 1e5 + 7;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const int base = 1<<18;
const int LOG = 18;
const int A = 26;
const int PROD = 2 * MAXN;
const int MAX = 2e3 + 7;
const int SQ = 220;

struct interval {
	
	int lo, hi, mid;
};

vector<pair<int, int>> G[MAXN];
vector<int> mids[MAXN];
pair<int, int> checkpoints[MAXN];
tuple<int, int, int, int> que[MAXN];
pii tree[2 * base];
int queriesLCA[MAXN];
int pre[MAXN], post[MAXN];
int jmp[MAXN][LOG];
int edges[MAXN];
int depth[MAXN];
int ans[MAXN];
interval bin[MAXN];
int c = 0;
int n, m, q;


void update(int v, pair<int, int> val){
	
	v += base;
	tree[v].fi += val.fi;
	tree[v].se += val.se;
	v /= 2;
	
	while(v > 0){
		
		tree[v] = {tree[2 * v].fi + tree[2 * v + 1].fi, tree[2 * v].se + tree[2 * v + 1].se};
		v /= 2;	
	}
}


pair<int, int> query(int a, int b){
	
	a += base - 1;
	b += base + 1;
	
	pair<int, int> res = {0, 0};
	
	while(a/2 != b/2){
		
		if(a%2 == 0){
			
			res.fi += tree[a + 1].fi;
			res.se += tree[a + 1].se;
		}
		
		if(b%2 == 1){
			
			res.fi += tree[b - 1].fi;
			res.se += tree[b - 1].se;
		}
		
		a /= 2; b /= 2;
	}
	
	return res;
}


void DFS(int v, int p){
	
	depth[v] = depth[p] + 1;
	pre[v] = ++c;
	jmp[v][0] = p;
	
	for(int j = 1; j < LOG; j++){
		
		jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
	}
	
	for(auto [u, ind] : G[v]){
		
		if(u == p) continue;
		edges[ind] = u;
		DFS(u, v);
	}
	
	post[v] = ++c;
}


int lca(int u, int v){
	
	if(depth[u] < depth[v]) swap(u, v);
	int diff = depth[u] - depth[v];
	
	for(int i = 0; i < LOG; i++){
    	
        if((1<<i) & diff){
        	
        	u = jmp[u][i];
		}
    }
	
	if(u == v) return u;
	
	for(int i = LOG - 1; i >= 0; i--){
		
		if(jmp[u][i] != jmp[v][i]){
			
			u = jmp[u][i];
			v = jmp[v][i];
		}
	}
	
	return jmp[v][0];
}


void treeclear(){
	
	for(int i = 0; i < 2 * base; i++){
		
		tree[i] = {0, 0};
	}
}

bool check(tuple<int, int, int, int> a, int v){
	
	auto [s, t, x, y] = a;
	
	if(depth[t] < depth[s]) swap(s, t);
	
	pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.fi -= tree[pre[queriesLCA[v]] + base].fi;
	res.se -= tree[pre[queriesLCA[v]] + base].se;
	
	if(queriesLCA[v] != s){
		
		pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
		x.fi -= tree[pre[queriesLCA[v]] + base].fi;
		x.se -= tree[pre[queriesLCA[v]] + base].se;
		
		res.fi += x.fi;
		res.se += x.se;
	}
	
	return res.fi <= y;
}



void parallel_binsearch(){
	
	int left = q;
	
	while(left){
		
		for(int i = 0; i <= m; i++){
		
			update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
			update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
			
			for(auto cand : mids[i]){
				
				if(check(que[cand], cand)) bin[cand].lo = i + 1;
				else bin[cand].hi = i;
				
				bin[cand].mid = (bin[cand].lo + bin[cand].hi)/2;
				
				if(bin[cand].lo == bin[cand].hi) left--;
				else mids[bin[cand].mid].push_back(cand);
			}
			
			mids[i].clear();
		}
		
		treeclear();
	}
}


void save_res(int v, bool save){
	
	auto [s, t, x, y] = que[v];
	
	if(depth[t] < depth[s]) swap(s, t);
	
	pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.fi -= tree[pre[queriesLCA[v]] + base].fi;
	res.se -= tree[pre[queriesLCA[v]] + base].se;
	
	if(queriesLCA[v] != s){
		
		pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
		x.fi -= tree[pre[queriesLCA[v]] + base].fi;
		x.se -= tree[pre[queriesLCA[v]] + base].se;
		
		res.fi += x.fi;
		res.se += x.se;
	}
	
	if(save){
		
		ans[v] = res.se;
		if(res.fi > y) ans[v] = max(ans[v] - 1, 0LL);
	}
	
	else ans[v] = x - max(0LL, res.se - ans[v]);
}




void rozw(){
	
	for(int i = 1; i <= q; i++){
		
		mids[bin[i].lo].push_back(i);
	}
	
	for(int i = 0; i <= m; i++){
		
		update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
		update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
		
		for(auto cand : mids[i]){
			
			save_res(cand, 1);
		}
		
		mids[i].clear();
	}
	
	for(int i = 1; i <= q; i++){
	
		save_res(i, 0);
	}
}



void solve(){
	
	cin >> n >> m >> q;
	
	for(int i = 1; i < n; i++){
		
		int a, b;
		cin >> a >> b;
		G[a].push_back({b, i});
		G[b].push_back({a, i});
	}
	
	for(int i = 1; i <= m; i++){
		
		int p, c;
		cin >> p >> c;
		checkpoints[i] = {c, p};
	}
	
	DFS(1, 1);
	
	for(int i = 1; i <= q; i++){
		
		int s, t, x, y;
		cin >> s >> t >> x >> y;
		
		que[i] = {s, t, x, y};
		queriesLCA[i] = lca(s, t);
		bin[i].lo = 0;
		bin[i].hi = m;
		bin[i].mid = m/2;
		mids[bin[i].mid].push_back(i);
	}
	
	sort(checkpoints + 1, checkpoints + m + 1);
	parallel_binsearch();
	rozw();
	
	for(int i = 1; i <= q; i++){
		
		cout << max(ans[i], -1LL) << '\n';
	}	
}

bool multi = 0;
 
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int t = 1;
	if(multi) cin >> t;
	
	while(t--) solve();
	
	return 0;
}

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