Submission #761863

#	Time	Username	Problem	Language	Result	Execution time	Memory
761863		sentheta	Two Currencies (JOI23_currencies)	C++17	100 / 100	2072 ms	80732 KiB

currencies

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}












const int N = 1e5+5;
const int LN = 18;

int n, m, q;

pii edg[N];
V<int> adj[N];

int root;

// regular euler tour
int dep[N], in[N], out[N], tim=1;
void dfs_init(int x=root,int par=0){
	in[x] = tim++;
	for(int y : adj[x]) if(y!=par){
		dep[y] = dep[x]+1;
		dfs_init(y, x);
	}
	out[x] = tim-1;
}

// lca sparse table
// duplicated euler tour
int getMinDepth(int x,int y){
	return (dep[x]<dep[y]) ? x : y;
}
struct Stable{
	int v[2*N][LN];
	void build(){
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<2*N; i++){
			v[i][lg] = getMinDepth(v[i][lg-1], v[i+(1<<(lg-1))][lg-1]);
		}
	}
	int qry(int l,int r){
		int lg = __lg(r-l+1);
		return getMinDepth(v[l][lg], v[r-(1<<lg)+1][lg]);
	}
} stable;
int st[N], stim=1;
int getLca(int x,int y){
	if(!(st[x]<st[y])) swap(x,y);
	return stable.qry(st[x], st[y]);
}
void dfs_stable(int x=root,int par=0){
	st[x] = stim;
	stable.v[stim++][0] = x;
	for(int y : adj[x]) if(y!=par){
		dfs_stable(y, x);
		stable.v[stim++][0] = x;
	}
}

// fenwick tree, range update, point query
struct Fenw{
	// int v[N];
	// void reset(){
	// 	rep(i,0,N) v[i] = 0;
	// }
	// void upd(int l,int r,int val){
	// 	for(l++; l<N; l+=l&-l) v[l]+=val;
	// 	r++;
	// 	for(r++; r<N; r+=r&-r) v[r]-=val;
	// }
	// int qry(int i){
	// 	int ret = 0;
	// 	for(i++; i; i-=i&-i) ret+=v[i];
	// 	return ret;
	// }

	#define lc (v+1)
	#define rc (v+2*(mid-tl+1))
	#define mid (tl+tr)/2
	int lz[2*N];
	void reset(){
		rep(v,0,2*N) lz[v] = 0;
	}
	void upd(int l,int r,int val,int v=0,int tl=1,int tr=n){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			lz[v] += val; return;
		}
		upd(l,r,val, lc,tl,mid);
		upd(l,r,val, rc,mid+1,tr);
	}
	int qry(int i,int v=0,int tl=1,int tr=n){
		if(tl==tr) return lz[v];
		if(i<=mid) return lz[v] + qry(i, lc,tl,mid);
		else return lz[v] + qry(i, rc,mid+1,tr);
	}

	int getInPath(int x,int y){
		return qry(in[x]) + qry(in[y]) - 2*qry(in[getLca(x,y)]);
	}
	#undef lc
	#undef rc
	#undef mid
} counter, silver;


// tax position and cost
int pos[N], c[N];

// queries	
int qs[N], qt[N], qx[N], qy[N];
// max #taxes paid by silver
int qans[N];
// range to check
int ql[N], qr[N];
// queries to check
V<int> tochk[N];

void solve(){
	
	cin >> n >> m >> q;
	
	// input edges
	rep(e,1,n){
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
		edg[e] = {u,v};
	}

	root = rng()%n+1;
	dfs_init();
	assert(tim-1==n);

	dfs_stable();
	assert(stim-1==2*n-1);
	stable.build();
	// rep(i,1,n+1) assert(getLca(i,i)==i);
	
	// input taxes
	V<int> txord;
	rep(i,0,m){
		cin >> pos[i] >> c[i];

		txord.push_back(i);

		// put this tax at child
		auto[u,v] = edg[pos[i]];
		pos[i] = u ^ v ^ getMinDepth(u,v);
	}
	sort(all(txord),[&](int i,int j){
		return c[i] < c[j];
	});
	
	// input queries
	rep(i,1,q+1){
		cin >> qs[i] >> qt[i] >> qx[i] >> qy[i];

		qans[i] = 0;
		ql[i] = 0; qr[i] = m-1;
	}

	// silver.getInPath(1,2);
	// return;


	// parallel binsearch
	while(1){
	// rep(loop,0,LN){
		// dbg(loop);

		bool unsolved = 0;
		rep(i,0,m) tochk[i].clear();
		rep(i,1,q+1) if(ql[i]<=qr[i]){
			tochk[(ql[i]+qr[i])/2].push_back(i);
			unsolved = 1;
		}
		if(!unsolved) break;

		counter.reset();
		silver.reset();

		// insert taxes
		rep(i,0,m){
			// dbg(i);

			// insert tax into euler tour
			int idx = txord[i]; // tax ID
			int x = pos[idx];
			counter.upd(in[x], out[x], 1);
			silver.upd(in[x], out[x], c[idx]);

			// check queries
			for(int j : tochk[i]){
				// check whether have enough silver
				if(silver.getInPath(qs[j],qt[j]) <= qy[j]){
					qans[j] = counter.getInPath(qs[j],qt[j]);
					ql[j] = i+1;
				}
				else{
					qr[j] = i-1;
				}
			}
		}

	}

	counter.reset();
	rep(idx,0,m){
		int x = pos[idx];
		counter.upd(in[x], out[x], 1);
	}

	// output answer
	rep(i,1,q+1){
		int ans = qx[i]+qans[i] - counter.getInPath(qs[i],qt[i]);
		ans = max(ans, -1LL);
		cout << ans << nl;
	}
}

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