Submission #839239

#	Time	Username	Problem	Language	Result	Execution time	Memory
839239		starplat	Two Currencies (JOI23_currencies)	C++14	10 / 100	3534 ms	66052 KiB

currencies

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int n,m,q,u[100005],v[100005],road[100005],pos[400005];
int tin,in[200005],out[200005],lift[25][200005],szm,szq;
int l[100005],r[100005],gold[100005],sil[100005],vis[100005];
int frq[100005],bkfq[100005],sum[100005],ans[100005];
pair<int,int> ckpt[100005];
vector<pair<int,int> > grh[200005];
vector<int> st[100005];
pair<int,pair<int,int> > qry[100005];
void add(int x,int y,int w){
	grh[x].push_back({y,w});
	grh[y].push_back({x,w});
}
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.f==p) continue;
		road[i.f]=i.second;
		dfs(i.f,x);
	}
	out[x]=++tin;
	pos[in[x]]=pos[out[x]]=x;
}
bool cmp(pair<int,pair<int,int>> x,pair<int,pair<int,int>> y){
	if (x.s.f/szq!=y.s.f/szq) return x.s.f<y.s.f;
	else return x.s.s<y.s.s;
}
int blck(int x){
	return x/szm+(x%szm>0LL);
}
void upd(int x){
	x=pos[x];
	vis[x]^=1LL;
	if (!road[x]) return;
	if (vis[x]){
	  //  cout<<"add "<<road[x]<<" "<<x<<'\n';
		frq[road[x]]++; bkfq[blck(road[x])]++;
		sum[blck(road[x])]+=ckpt[road[x]].f;
	}
	else {
	    //cout<<"del "<<road[x]<<" "<<x<<"\n";
		frq[road[x]]--; bkfq[blck(road[x])]--;
		sum[blck(road[x])]-=ckpt[road[x]].f;
	}
}
signed main(){
	cin>>n>>m>>q;
	szm=(int)sqrt(n); szq=(int)sqrt(q);
	for (int i=1;i<n;i++) cin>>u[i]>>v[i];
	for (int i=1;i<=m;i++) cin>>ckpt[i].s>>ckpt[i].f;
	sort(ckpt+1,ckpt+1+m);
	for (int i=1;i<=m;i++){
		st[ckpt[i].s].push_back(i);
	}
	for (int i=1;i<n;i++){
		if (st[i].empty()) {
		    add(u[i],v[i],0);
		    continue;
		}
		int curr=u[i];
		for (int j=0;j<st[i].size()-1;j++) {
			add(curr,n+st[i][j],st[i][j]);
			curr=n+st[i][j];
		}
		add(curr,v[i],st[i].back());
	}
	dfs(1,0);
	for (int i=1;i<=q;i++){
		cin>>l[i]>>r[i]>>gold[i]>>sil[i];
		if (in[l[i]]>in[r[i]]) swap(l[i],r[i]);
		int anc=lca(l[i],r[i]);
		qry[i].f=i;
		if (l[i]==anc) qry[i].s={in[l[i]],in[r[i]]};
		else qry[i].s={out[l[i]],in[r[i]]};
	}
	sort(qry+1,qry+1+q,cmp);
	int ptr=0; int ptl=1;
	for (int i=1;i<=q;i++){
		while (ptr>qry[i].s.s) upd(ptr--);
		while (ptr<qry[i].s.s) upd(++ptr);
		while (ptl>qry[i].s.f) upd(--ptl);
		while (ptl<qry[i].s.f) upd(ptl++);
		int anc=lca(l[qry[i].f],r[qry[i].f]);
		bool ok=false;
		if (l[qry[i].f]==anc) upd(in[anc]);
		for (int j=1;j<=blck(m);j++){
			if (ok) ans[qry[i].f]+=bkfq[j];
			else if (sum[j]<=sil[qry[i].f]) sil[qry[i].f]-=sum[j];
			else {
				ok=true;
				for (int k=szm*(j-1)+1;k<=min(m,szm*j);k++){
					int d=min(sil[qry[i].f]/ckpt[k].f,frq[k]);
					sil[qry[i].f]-=d*ckpt[k].f;
					ans[qry[i].f]+=frq[k]-d;
				}
			}
		}
		if (l[qry[i].f]==anc) upd(in[anc]);
	}
	for (int i=1;i<=q;i++){
	   // cout<<sil[i]<<" ";
		if (ans[i]>gold[i]) cout<<"-1\n";
		else cout<<gold[i]-ans[i]<<"\n";
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:77:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int j=0;j<st[i].size()-1;j++) {
      |                ~^~~~~~~~~~~~~~~

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