Submission #1308094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308094		nguyenletrung	Two Currencies (JOI23_currencies)	C++20	100 / 100	2990 ms	68136 KiB

currencies

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define int ll
using namespace std;
int n,m,nq;
int cnt,tt[100005],sz[100005],lca[20][100005],dep[100005];
int a[100005],b[100005],G[100005],S[100005],L[100005],R[100005],MID[100005],ANS[100005],PAR[100005];
vector<int> adj[100005],tram[100005],query[100005];
vector<pair<int,int>> vv;
pair<int,int> canh[100005];

void dfs(int u,int par)
{
	cnt++;
	tt[u]=cnt;
	sz[u]=1;
	for(auto v:adj[u])
	{
		if(v==par) continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
		lca[0][v]=u;
		sz[u]+=sz[v];
	}
}

void buildd()
{
	for(int i=1;i<=17;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(dep[u]<dep[v]) swap(u,v);
	
	ford(i,17,0)
	{
		if(dep[lca[i][u]]>=dep[v])
		{
			u=lca[i][u];
		}
	}
	
	if(u==v) return u;
	else
	{
		ford(i,17,0)
		{
			if(lca[i][u]!=lca[i][v])
			{
				u=lca[i][u];
				v=lca[i][v];
			}
		}
		
		return lca[0][u];
	}
}

struct IT{
	int t[400005],lz[400005];
	
	void build(int id,int l,int r)
	{
		if(l==r)
		{
			t[id]=0;
//			lz[id]=0;
			return;
		}
		
		int mid=(l+r)/2;
		
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		
		t[id]=0;
//		lz[id]=0;
	}
	
	void push(int id)
	{
		if(t[id]==0) return;
		t[id*2]+=t[id];
		t[id*2+1]+=t[id];
		
//		lz[id*2]+=lz[id];
//		lz[id*2+1]+=lz[id];
		
		t[id]=0;
	}
	
	void update(int id,int l,int r,int u,int v,int w)
	{
		if(r<u||v<l) return;
		
		if(u<=l&&r<=v)
		{
			t[id]+=w;
//			lz[id]+=w;
			return;
		}
		
		push(id);
		int mid=(l+r)/2;
		
		update(id*2,l,mid,u,v,w);
		update(id*2+1,mid+1,r,u,v,w);
		
//		t[id]=t[id*2]+t[id*2+1];
	}
	
	int get(int id,int l,int r,int pos)
	{
		if(pos<l||r<pos) return 0;
		
		if(l==r)
		{
			return t[id];
		}
		
		push(id);
		int mid=(l+r)/2;
		
		return get(id*2,l,mid,pos)+get(id*2+1,mid+1,r,pos);
	}
};

IT gold,silver;

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m>>nq;
	
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
		canh[i]={x,y};
	}
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		tram[a].pb(b);
		vv.pb({b,a});
	}
	vv.pb({0,0});
	
	sort(vv.begin(),vv.end());
	
	dep[1]=1;
	dfs(1,0);
	buildd();
	
	for(int i=1;i<=nq;i++)
	{
		cin>>a[i]>>b[i]>>G[i]>>S[i];
		PAR[i]=getlca(a[i],b[i]);
		L[i]=0;
		R[i]=m;
	}
	
	int cc=17;
	
	while(cc--)
	{
		gold.build(1,1,n);
		silver.build(1,1,n);
		
		foru(i,0,m)
		{
			query[i].clear();
		}
		
		foru(i,1,m)
		{
			int ss=vv[i].fi,id=vv[i].se;
			
			int a=canh[id].fi,b=canh[id].se;
			
			if(dep[a]<dep[b]) swap(a,b);
			
			gold.update(1,1,n,tt[a],tt[a]+sz[a]-1,1);
		}
		
		foru(i,1,nq)
		{
			if(L[i]>R[i]) continue;
			MID[i]=(L[i]+R[i])/2;
			
			query[MID[i]].pb(i);
		}
		
		for(int i=0;i<=m;i++)
		{
			int ss=vv[i].fi,id=vv[i].se;
			
			int aa=canh[id].fi,bb=canh[id].se;
			
			if(dep[aa]<dep[bb]) swap(aa,bb);
			
			gold.update(1,1,n,tt[aa],tt[aa]+sz[aa]-1,-1);
			silver.update(1,1,n,tt[aa],tt[aa]+sz[aa]-1,ss);
			
			for(auto ID:query[i])
			{	
				
				int par=PAR[ID];
				
				int needgold=gold.get(1,1,n,tt[a[ID]])+gold.get(1,1,n,tt[b[ID]])-2*gold.get(1,1,n,tt[par]);
				int needsilver=silver.get(1,1,n,tt[a[ID]])+silver.get(1,1,n,tt[b[ID]])-2*silver.get(1,1,n,tt[par]);
				
				if(needsilver<=S[ID])
				{
					ANS[ID]=needgold;
					L[ID]=MID[ID]+1;
				}
				else
				{
					R[ID]=MID[ID]-1;
				}
			}
		}
	}
	
	for(int i=1;i<=nq;i++)
	{
		if(ANS[i]<=G[i])
		{
			cout<<G[i]-ANS[i]<<'\n';
		}
		else
		{
			cout<<-1<<'\n';
		}
	}
	
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

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