Submission #874332

#	Time	Username	Problem	Language	Result	Execution time	Memory
874332		Hakiers	Two Currencies (JOI23_currencies)	C++17	100 / 100	988 ms	44520 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 7;
constexpr int BASE = 1 << 18;
struct ext{
	int lo, hi, mid;
};
vector<pair<int, int>> G[MAXN];
vector<int> mids[MAXN];
pair<int, int> checkpoints[MAXN];
tuple<int, int, int, ll> Queries[MAXN];
pair<ll, int> TREE[BASE << 1];
int queriesLCA[MAXN];
int pre[MAXN], post[MAXN];
int jmp[MAXN][18];
int edges[MAXN];
int depth[MAXN];
int anserw[MAXN];
ext bin[MAXN];
int tajm;
int n, m, q;

void update(int v, pair<ll, int> val){
	v += BASE;
	TREE[v].first += val.first;
	TREE[v].second += val.second;
	v/=2;
	
	while(v > 0){
		int l = 2*v, r = 2*v+1;
		TREE[v].first = TREE[l].first + TREE[r].first;
		TREE[v].second = TREE[l].second + TREE[r].second;
		v/=2;
	}
}

pair<ll, int> query(int a, int b){
	a += BASE - 1;
	b += BASE + 1;
	
	pair<ll, int> res = {0, 0};
	
	while(a/2 != b/2){
		
		if(a%2 == 0){
			res.first += TREE[a+1].first;
			res.second += TREE[a+1].second;
		}
		if(b%2 == 1){
			res.first += TREE[b-1].first;
			res.second += TREE[b-1].second;
		}
		a/=2; b/=2;
	}
	
	return res;
}

void dfs(int v, int p){
	depth[v] = depth[p] + 1;
	pre[v] = ++tajm;
	jmp[v][0] = p;
	for(int k = 1; k <= 17; k++)
		jmp[v][k] = jmp[jmp[v][k-1]][k-1];
	
	for(auto [u, id] : G[v]){
		if(u == p) continue;
		edges[id] = u;
		dfs(u, v);
	}

	post[v] = ++tajm;
}

int lca(int v, int u){
	if(depth[u] < depth[v]) swap(u, v);
	
	for(int k = 17; k >= 0; k--)
		if(depth[jmp[u][k]] >= depth[v])
			u = jmp[u][k];
	
	if(v == u) return v;
	
	for(int k = 17; k >= 0; k--){
		if(jmp[u][k] != jmp[v][k]){
			u = jmp[u][k];
			v = jmp[v][k];
		}
	}
	
	return jmp[v][0];
}

void treeclear(){
	for(int i = 0; i < (BASE << 1); i++)
		TREE[i] = {0, 0};
}

bool check(tuple<int, int, int, ll> a, int v){
	
	auto [s, t, x, y] = a;
	
	if(depth[t] < depth[s]) swap(s, t);
	
	pair<ll, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.first -= TREE[pre[queriesLCA[v]] + BASE].first;
	res.second -= TREE[pre[queriesLCA[v]] + BASE].second;
	
	if(queriesLCA[v] != s){
		pair<ll, int> xd = query(pre[queriesLCA[v]], pre[s]);
		xd.first -= TREE[pre[queriesLCA[v]] + BASE].first;
		xd.second -= TREE[pre[queriesLCA[v]] + BASE].second;
		
		res.first += xd.first;
		res.second += xd.second;
	}
	
	if(res.first <= y) return true;
	return false;
}


void parallel_solve(){
	int zostalo = q;
	while(zostalo){
		for(int i = 0; i <= m; i++){
			update(pre[edges[checkpoints[i].second]], {checkpoints[i].first, 1});
			update(post[edges[checkpoints[i].second]], {-checkpoints[i].first, -1});
			
			for(auto candidate : mids[i]){
				if(check(Queries[candidate], candidate)) bin[candidate].lo = i + 1;
				else bin[candidate].hi = i;
				
				bin[candidate].mid = (bin[candidate].lo + bin[candidate].hi)/2;
				
				if(bin[candidate].lo == bin[candidate].hi) zostalo--;
				else mids[bin[candidate].mid].push_back(candidate);
			}
			
			mids[i].clear();
			mids[i].shrink_to_fit();
		}
		treeclear();
	}
}

void save_res(int v, bool save){
	
	auto [s, t, x, y] = Queries[v];
	if(depth[t] < depth[s]) swap(s, t);
	pair<ll, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.first -= TREE[pre[queriesLCA[v]] + BASE].first;
	res.second -= TREE[pre[queriesLCA[v]] + BASE].second;
		
	if(queriesLCA[v] != s){
		pair<ll, int> xd = query(pre[queriesLCA[v]], pre[s]);
		xd.first -= TREE[pre[queriesLCA[v]] + BASE].first;
		xd.second -= TREE[pre[queriesLCA[v]] + BASE].second;
		
		res.first += xd.first;
		res.second += xd.second;
	}
	
	if(save){ 
		anserw[v] = res.second;
		if(res.first > y) anserw[v] = max(anserw[v]-1, 0);
	}
	else anserw[v] = x - max(0, res.second - anserw[v]);
}

void solve(){
	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].second]], {checkpoints[i].first, 1});
		update(post[edges[checkpoints[i].second]], {-checkpoints[i].first, -1});
		for(auto candidate : mids[i])
			save_res(candidate, 1);
		mids[i].clear();
		mids[i].shrink_to_fit();
	}
	
	for(int i = 1; i <= q; i++)
		save_res(i, 0);
		
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	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;
		ll y;
		cin >> s >> t >> x >> y;
		Queries[i] = {s, t, x, y};
		queriesLCA[i] = lca(s, t);
		bin[i].lo = 0;
		bin[i].hi = m;
		bin[i].mid = (0+m)/2;
		mids[bin[i].mid].push_back(i);
	}
	
	sort(checkpoints + 1, checkpoints + 1 + m);
	parallel_solve();
	solve();
	
	for(int i = 1; i <= q; i++)
		cout << max(anserw[i], -1) << "\n";
	
}

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