Submission #953920

#	Time	Username	Problem	Language	Result	Execution time	Memory
953920		amirhoseinfar1385	Two Currencies (JOI23_currencies)	C++17	100 / 100	654 ms	45600 KiB

currencies

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn=100000+10,lg=17;
struct qu{
	int u,v,y,uv;
	long long x;
}allq[maxn];
int n,m,q,lca[lg][maxn],timea,kaf=(1<<17),high[maxn],low[maxn],mid[maxn],check[maxn],len[maxn],res[maxn];
vector<int>adj[maxn];
vector<pair<int,int>>allc;
pair<int,int>stf[maxn],heye[maxn];

struct segment{
	long long seg[(1<<18)];
	void clear(){
		for(int i=0;i<(1<<18);i++){
			seg[i]=0;
		}
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]+=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	long long pors(int i){
		i+=kaf;
		long long ret=0;
		while(i>0){
			ret+=seg[i];
			i>>=1;
		}
		return ret;
	}
}seg;

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

void vorod(){
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		heye[i]=make_pair(u,v);
	}
	allc.resize(m);
	for(int i=0;i<m;i++){
		cin>>allc[i].second>>allc[i].first;
	}
	for(int i=0;i<q;i++){
		cin>>allq[i].u>>allq[i].v>>allq[i].y>>allq[i].x;
	}
}

void dfs(int u,int par=-1){
	timea++;
	stf[u].first=timea;
	if(par!=-1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	for(auto x:adj[u]){
		lca[0][x]=u;
		len[x]=len[u]+1;
		dfs(x,u);
	}
	stf[u].second=timea;
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

void pre(){
	sort(allc.begin(),allc.end());
	dfs(1);
	callca();
	for(int i=0;i<m;i++){
		int te=allc[i].second;
		if(len[heye[te].first]<len[heye[te].second]){
			allc[i].second=heye[te].second;
		}else{
			allc[i].second=heye[te].first;
		}
	}
	for(int i=0;i<q;i++){
		allq[i].uv=getlca(allq[i].u,allq[i].v);
	}
	for(int i=0;i<q;i++){
		low[i]=0;
		high[i]=maxn-2;
	}
}

void checkasl(int ind){
	long long w=seg.pors(stf[allq[ind].u].first)+seg.pors(stf[allq[ind].v].first)-2*seg.pors(stf[allq[ind].uv].first);
	check[ind]=(w<=allq[ind].x);
}
vector<int>allm[maxn];

void calcheck(){
	for(int i=0;i<q;i++){
		allm[mid[i]].push_back(i);
	}
	seg.clear();
	for(int i=0;i<=m;i++){
		for(auto x:allm[i]){
			checkasl(x);
		}
		if(i<m){
			auto x=allc[i];
			seg.upd(1,0,kaf-1,stf[x.second].first,stf[x.second].second,x.first);
		}
	}
	for(int i=0;i<q;i++){
		allm[mid[i]].clear();
	}
}

void solve(){
	for(int asd=0;asd<17;asd++){
		for(int i=0;i<q;i++){
			//cout<<i<<endl;
			mid[i]=(high[i]+low[i])/2;
			check[i]=0;
		}
		calcheck();
		for(int i=0;i<q;i++){
			if(check[i]){
				low[i]=mid[i];
			}else{
				high[i]=mid[i];
			}
		}
	}
}

void khor(){
	seg.clear();
	for(int i=0;i<q;i++){
		allm[low[i]].push_back(i);
	}
	for(int i=m;i>=0;i--){
		if(i<m)
		seg.upd(1,0,kaf-1,stf[allc[i].second].first,stf[allc[i].second].second,1);
		for(auto x:allm[i]){
			res[x]=seg.pors(stf[allq[x].u].first)+seg.pors(stf[allq[x].v].first)-2*seg.pors(stf[allq[x].uv].first);
		}	
	}
	for(int i=0;i<q;i++){
		int ret=max(-1,allq[i].y-res[i]);
		cout<<ret<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

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