Submission #1130017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130017		Math4Life2020	Two Currencies (JOI23_currencies)	C++20	10 / 100	1333 ms	866480 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5+5; const ll E = 18;
const ll INF = 1e18;

struct Node {
	//map<ll,ll> m0; //cost->number
	//map<ll,pii> mps; //aggregate: cost -> {# <=cost, val <=cost}
	vector<pii> m0;
	vector<array<ll,3>> mps;
	ll ncp = 0;
	void prc() {
		ll n0=0; ll v0=0;
		//mps[-INF]={0,0};
		mps.push_back({-INF,0LL,0LL});
		for (pii p0: m0) {
			ll c1 = p0.first; ll n1 = p0.second;
			n0+=n1; v0+=n1*c1;
			//mps[c1]={n0,v0};
			mps.push_back({c1,n0,v0});
		}
	}
	Node(){}
	Node(vector<ll> v1) {
		map<ll,ll> mtest;
		for (ll x: v1) {
			mtest[x]++;
		}
		ncp = v1.size();
		for (pii p0: mtest) {
			m0.push_back(p0);
		}
		prc();
	}
	Node(Node n1, Node n2) {
		map<ll,ll> mtest;
		for (pii p0: n1.m0) {
			mtest[p0.first]+=p0.second;
		}
		for (pii p0: n2.m0) {
			mtest[p0.first]+=p0.second;
		}
		ncp = n1.ncp+n2.ncp;
		for (pii p0: mtest) {
			m0.push_back(p0);
		}
		prc();
	}
	pii qry(ll x) {
		auto A0 = --upper_bound(mps.begin(),mps.end(),(array<ll,3>){x,INF,INF});
		return {(*A0)[1],(*A0)[2]};
	}
};

ll bjump[Nm][E];
Node ejump[Nm][E];
pii ett[Nm][E];
vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll radj[Nm];
ll locr[Nm]; //location of road (aka location of child)
ll ht[Nm];
ll floc[Nm];

inline ll gp(ll x, ll e) {
	if (x<0) {
		return x;
	}
	return bjump[x][e];
}

inline pii fz(pii p1, pii p2) {
	if (p1.second<p2.second) {
		return p1;
	} else {
		return p2;
	}
}

inline ll l2(ll x) {
	return (31-__builtin_clz(x));
}

inline ll v2(ll x) {
	return __builtin_ctz(x);
}

ll lca(ll x, ll y) {
	x = floc[x]; y = floc[y];
	if (x>y) {
		swap(x,y);
	}
	ll lv = l2(y-x+1);
	return (fz(ett[x][lv],ett[y-(1<<lv)+1][lv]).first);
}

pii ginf(vector<Node*>& v1, ll cst) {
	pii vf = {0,0};
	for (auto A0: v1) {
		pii v2 = A0->qry(cst);
		vf = {vf.first+v2.first,vf.second+v2.second};
	}
	return vf; //{number, total cost}
}

ll qry(vector<Node*>& v1, ll y) {
	ll xmin = 0; ll xmax = 1e10;
	//first binary search for the largest value of xtest
	//for which ginf(xtest).second <= y
	//store pair at this value
	while (xmin < xmax) {
		ll xtest = (xmin+xmax+1)/2;
		if ((ginf(v1,xtest).second)<=y) {
			xmin = xtest;
		} else {
			xmax = xtest-1;
		}
	}
	pii p1 = ginf(v1,xmin);
	pii p2 = ginf(v1,xmin+1);
	if (p1.first==p2.first || p1.second==y) {
		return p1.first;
	} else {
		ll vext = y-p1.second;
		ll cst = (p2.second-p1.second)/(p2.first-p1.first);
		//assert(cst==(xmin+1));
		return (p1.first+vext/cst);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M,Q; cin >> N >> M >> Q;
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b;
		a--; b--;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
	}
	radj[0]=-1;
	ht[0]=0;
	queue<ll> q0;
	q0.push(0);
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		for (pii p0: adj[x]) {
			ll y = p0.first;
			if (y != radj[x]) {
				fadj[x].push_back(y);
				radj[y]=x;
				locr[p0.second]=y;
				q0.push(y);
				ht[y]=1+ht[x];
			}
		}
	}
	vector<ll> ettv;
	stack<pii> st0;
	st0.push({0,0});
	while (!st0.empty()) {
		pii p0 = st0.top(); st0.pop();
		ll x = p0.first; ll t = p0.second;
		ettv.push_back(x);
		if (t==0) {
			floc[x]=ettv.size()-1;
			for (ll y: fadj[x]) {
				st0.push({x,1});
				st0.push({y,0});
			}
		}
	}
	for (ll i=0;i<ettv.size();i++) {
		ett[i][0]={ettv[i],ht[ettv[i]]};
	}
	for (ll e=1;e<E;e++) {
		for (ll i=0;i<=(Nm-(1<<e));i++) {
			ett[i][e]=fz(ett[i][e-1],ett[i+(1<<(e-1))][e-1]);
		}
	}
	if (N>2000) {
		for (ll q=0;q<Q;q++) {
			cout << "-2\n";
		}
		exit(0);
	}
	vector<ll> costE[Nm];
	for (ll m=0;m<M;m++) {
		ll p,c; cin >> p >> c;
		p--;
		costE[locr[p]].push_back(c);
	}
	for (ll i=0;i<N;i++) {
		bjump[i][0]=radj[i];
	}
	for (ll i=0;i<N;i++) {
		ejump[i][0]=Node(costE[i]);
	}
	if (N<=2000) {
	for (ll e=1;e<E;e++) {
		for (ll i=0;i<N;i++) {
			if (bjump[i][e-1]==-1) {
				bjump[i][e]=bjump[i][e-1];
				ejump[i][e]=ejump[i][e-1];
			} else {
				bjump[i][e]=bjump[bjump[i][e-1]][e-1];
				ejump[i][e]=Node(ejump[i][e-1],ejump[bjump[i][e-1]][e-1]);
			}
		}
	}
	} else {
		exit(0);
	}
	for (ll q=0;q<Q;q++) {
		ll s,t,x,y; cin >> s >> t >> x >> y;
		s--; t--;
		if (s==t) {
			cout << x << "\n"; continue;
		}
		//exit(0);
		ll lc = lca(s,t);
		//cout << "lc="<<lc<<"\n"; exit(0);
		//cout << "lca of s,t="<<s<<","<<t<<" is "<<lc<<"\n";
		//ll dist0 = ht[s]+ht[t]-2*ht[lc];
		vector<Node*> vq;
		ll ntoll = 0;
		while (s != lc) {
			ll dht = ht[s]-ht[lc];
			ll ldh = l2(dht);
			vq.push_back(&ejump[s][ldh]);
			ntoll += ejump[s][ldh].ncp;
			s=bjump[s][ldh];
		}
		while (t != lc) {
			ll dht = ht[t]-ht[lc];
			ll ldh = l2(dht);
			vq.push_back(&ejump[t][ldh]);
			ntoll += ejump[t][ldh].ncp;
			t=bjump[t][ldh];
		}
		ll maxr = qry(vq,y);
		ll gused = max(0LL,ntoll-maxr);
		//cout << "ntoll,maxr="<<ntoll<<","<<maxr<<"\n";
		if (x<gused) {
			cout << "-1\n";
		} else {
			cout << (x-gused) <<"\n";
		}
		// cout << "maxr="<<maxr<<"\n";
		// cout << "dist0="<<dist0<<"\n";
		// if ((maxr+x)>=dist0) {
		// 	cout << (maxr+x-dist0) <<"\n";
		// } else {
		// 	cout << "-1\n";
		// }
	}
}

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