Submission #835007

#	Time	Username	Problem	Language	Result	Execution time	Memory
835007		starplat	Two Currencies (JOI23_currencies)	C++14	10 / 100	5103 ms	33628 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
int szq,szm;
int n,m,q,u,v,st[100005],ed[100005],road[100005],vis[100005],ptl,ptr;
int tin,in[100005],out[100005],lift[25][100005],id[100005];
long long gold[100005],sil[100005],freq[100005],sum[2005],bkfq[2005],ans[100005];
vector<pair<int,int> > grh[100005];
pair<int,pair<int,int> > qry[100005];
vector<int> ckpt[100005];
pair<long long,int> pc[100005];
int blck(int x){
	return x/szm+(x%szm>0);
}
bool is(int x,int y){
	return in[x]<=in[y] && out[x]>=out[y];
}
int lca(int x,int y){
	if (is(x,y)) return x;
	if (is(y,x)) return y;
	for (int i=20;i>=0;i--){
		if (lift[i][x] && !is(lift[i][x],y)) x=lift[i][x]; 
	}
	return lift[0][x];
}
void dfs(int x,int p){
	in[x]=++tin; lift[0][x]=p;
	for (int i=1;i<=20;i++) lift[i][x]=lift[i-1][lift[i-1][x]];
	for (pair<int,int> i:grh[x]){
		if (i.first==p) continue;
		road[i.first]=i.second;
		dfs(i.first,x); 
	}
	out[x]=++tin;
	id[out[x]]=id[in[x]]=x;
}
bool cmp(pair<int,pair<int,int> > x,pair<int,pair<int,int> > y){
	if (x.second.first/szq!=y.second.first/szq) return x.second.first<y.second.first;
	else return x.second.second<y.second.second;
}
void upd(int x){
	x=id[x];
//	if (vis[x]) cout<<"del :";
//	else cout<<"add :";
//	cout<<x<<"\n";
	if (vis[x]){
		vis[x]=0;
		if (road[x]) {
			for (int i:ckpt[road[x]]){
				freq[i]--; bkfq[blck(i)]--;
				sum[blck(i)]-=pc[i].first;
			}
		}
	} 
	else {
		vis[x]=1;
		if (road[x]){
			for (int i:ckpt[road[x]]){
				freq[i]++; bkfq[blck(i)]++;
				sum[blck(i)]+=pc[i].first;
			}
		}
	}
}
long long output(long long x){
	return (x<0LL?-1LL:x);
}
int main(){
	scanf("%d%d%d",&n,&m,&q); 
	szq=(int)sqrt(q); szm=(int)sqrt(m);
	for (int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		grh[u].emplace_back(make_pair(v,i));
		grh[v].emplace_back(make_pair(u,i));
	}
	dfs(1,0);
	for (int i=1;i<=m;i++) scanf("%d%lld",&pc[i].second,&pc[i].first);
	for (int i=1;i<=q;i++){
		scanf("%d%d%lld%lld",st+i,ed+i,gold+i,sil+i);
		int anc=lca(st[i],ed[i]);
		if (in[st[i]]>in[ed[i]]) swap(st[i],ed[i]);
		if (anc==st[i]) qry[i].second=make_pair(in[st[i]],in[ed[i]]);
		else qry[i].second=make_pair(out[st[i]],in[ed[i]]);
		qry[i].first=i; 
	}
	sort(qry+1,qry+1+q,cmp);
	sort(pc+1,pc+1+m);
	for (int i=1;i<=m;i++) ckpt[pc[i].second].push_back(i);
	ptl=1; ptr=0;
	for (int i=1;i<=q;i++){
		int l=st[qry[i].first]; int r=ed[qry[i].first];
		//cout<<l<<" "<<r<<"\n"<<qry[i].second.first<<" "<<qry[i].second.second<<"\n";
		while (ptr<qry[i].second.second) upd(++ptr);
		while (ptr>qry[i].second.second) upd(ptr--);
		while (ptl<qry[i].second.first) upd(ptl++);
		while (ptl>qry[i].second.first) upd(--ptl);
		int anc=lca(l,r);
		bool can=true;
		if (anc==l) upd(in[l]);
		for (int j=1;j<=blck(m);j++){
			if (!can) ans[qry[i].first]+=bkfq[j];
			else if (sum[j]<=sil[qry[i].first]) sil[qry[i].first]-=sum[j];
			else {
				can=false;
				for (int k=szm*(j-1)+1;k<=min(m,szm*j);k++){
					long long d=min(sil[qry[i].first]/pc[k].first,freq[k]);
					sil[qry[i].first]-=d*pc[k].first;
					ans[qry[i].first]+=freq[k]-d;
				}
			}
		}
		if (anc==l) upd(in[l]);
	}
	for (int i=1;i<=q;i++) printf("%lld\n",output(gold[i]-ans[i]));
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
currencies.cpp:76:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  for (int i=1;i<=m;i++) scanf("%d%lld",&pc[i].second,&pc[i].first);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d%lld%lld",st+i,ed+i,gold+i,sil+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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