Submission #961366

#	Time	Username	Problem	Language	Result	Execution time	Memory
961366		MarwenElarbi	Two Currencies (JOI23_currencies)	C++17	100 / 100	4683 ms	207096 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
vector<int>adj[100005];
int in[100005];
int out[100005];
int d[100005];
int two[25][100005];
int ptr=0;
int h[100005];
 
void dfs(int index, int par){
	in[index]=++ptr;
	for(int x=0;x<20;x++){
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(it==par) continue;
		two[0][it]=index;
		d[it]=d[index]+1;
		//h[it]+=h[index];
		dfs(it,index);
	}
	out[index]=++ptr;
}
 
void dfs2(int index, int par){
	for(auto it:adj[index]){
		if(it==par) continue;
		h[it]+=h[index];
		dfs2(it,index);
	}
}
 
int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<19;x++){
		if(diff&(1<<x)){
			b=two[x][b];
		}
	}
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][a]!=two[x][b]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
} 
 
int fw[200005];
int fw2[200005];
 
void upd(int x, int y, int z){
	while(x<200005){
		fw[x]+=y;
		fw2[x]+=z;
		x+=x&(-x);
	}
}
 
pii sum(int x){
	int counter=0;
	int counter2=0;
	while(x>0){
		counter+=fw[x];
		counter2+=fw2[x];
		x-=x&(-x);
	}
	return {counter,counter2};
}
 
void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	
	int temp,temp2;
	pii edge[n-1];
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
		edge[x]={temp,temp2};
	}
	
	dfs(1,-1);
	
	
	pii check[m+1]; //cost edge
	for(int x=1;x<=m;x++){
		cin >> check[x].second >> check[x].first;
		int index;
		int road=check[x].second-1;
		if(d[edge[road].first] > d[edge[road].second]){
			index=edge[road].first;
		}
		else index=edge[road].second;
		h[index]++;
		//show(index,index);
	}
	
	dfs2(1,-1);
	//for(int x=1;x<=n;x++){
		//show2(x,x,h[x],h[x]);
	//}
	
	sort(check+1,check+m+1);
	
	vector<array<int,5>>storage[m+1];
	vector<array<int,5>>storage2[m+1];
	
	
	int l[q];
	int r[q];
	int ans[q];
	for(int x=0;x<q;x++){
		int from,to,a,b;
		cin >> from >> to >> a >> b;
		array<int,5>take;
		take={from,to,a,b,x};
		storage[m/2].push_back(take);
		l[x]=0;
		r[x]=m;
		ans[x]=-1;
	}
	
	for(int k=0;k<21;k++){
		memset(fw,0,sizeof(fw));
		memset(fw2,0,sizeof(fw2));
		
		for(int x=0;x<=m;x++){
			if(x>0){
				int road=check[x].second-1;
				int index;
				if(d[edge[road].first] > d[edge[road].second]){
					index=edge[road].first;
				}
				else index=edge[road].second;
				
				upd(in[index],check[x].first,1);
				upd(out[index],-check[x].first,-1);
			}
			
			for(auto it:storage[x]){
				int from=it[0];
				int to=it[1];
				int a=it[2];
				int b=it[3];
				int id=it[4];
				
				int ant=lca(from,to);
				
				pii aa=sum(in[from]);
				pii bb=sum(in[to]);
				pii cc=sum(in[ant]);
				
				int val=aa.first + bb.first - 2*cc.first;
				if(val<=b){
					l[id]=x+1;
					int val2 = aa.second + bb.second - 2*cc.second;
					
					int len=h[from]+h[to]-h[ant]*2-val2;
					if(a-len>=0){
						ans[id]=max(ans[id],a-len);
					}
				}
				else{
					r[id]=x-1;
				}
				if(l[id]<=r[id]){
					storage2[(l[id]+r[id])/2].push_back(it);
				}
			}
		}
		
		for(int x=0;x<=m;x++){
			storage[x].clear();
			while(!storage2[x].empty()){
				storage[x].push_back(storage2[x].back());
				storage2[x].pop_back();
			}
		}
	}	
	
	for(int x=0;x<q;x++) cout << ans[x] << "\n";
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","w",stdout);
	//cin >> t;
	while(t--){
		solve();
	}
}

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