Submission #730486

#	Time	Username	Problem	Language	Result	Execution time	Memory
730486		kym	Two Currencies (JOI23_currencies)	C++14	28 / 100	608 ms	425444 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 1000005;
int n,m,q;
vector<int>V[MAXN];
vector<pi> adj[MAXN];
int P[MAXN];
int head[MAXN];
int heavy[MAXN];
int pos[MAXN];
int parent[MAXN];
int depth[MAXN];
int sz[MAXN];
int cnt=1;
vector<int> W[MAXN];
int dfs(int x, int p){ 
	sz[x]=1;
	parent[x]=p;
	int mx=0;
	for(auto v:adj[x])if(v.f!=p){
		depth[v.f]=depth[x]+1;
		int res=dfs(v.f,x);
		W[v.f]=V[v.s];
		if(res>mx){
			mx=res;
			heavy[x]=v.f;
		}
		sz[x]+=res;
	}
	return sz[x];
}

void decompose(int x, int h) {
	pos[x]=cnt++;
	head[x]=h;
	if(heavy[x]!=-1)decompose(heavy[x],h);
	for(auto v:adj[x]){
		if(v.f==parent[x]||v.f==heavy[x])continue;
		decompose(v.f,v.f);
	}
}

struct node {
	node *l=nullptr,*r=nullptr;
	int sum;
	int num;
	int s,e,m;
	node(int _s, int _e, int val,int numval) {
		s=_s;e=_e;
		m=(s+e)/2;
		sum=val;
		num=numval;
		return;
	}
	node(int _s, int _e, node *L, node *R) {
		s=_s;e=_e;m=(s+e)/2;
		l=L;
		r=R;
		sum=0;
		num=0;
		if(l)sum+=l->sum;
		if(r)sum+=r->sum;
		if(l)num+=l->num;
		if(r)num+=r->num;
	}
} *roots[MAXN];

node* build(int tl, int tr){
	if(tl==tr){
		return new node(tl,tr,(int)0,(int)0);
	}
	int tm=(tl+tr)/2;
	return new node(tl,tr,build(tl,tm), build(tm+1,tr));
}

node* update(node *v, int tl, int tr, int pos, int nval) {
	if(tl==tr){
		return new node(tl,tr,v->sum+nval,v->num+1);
	}
	int tm=(tl+tr)/2;
	if(pos<=tm){
		return new node(tl,tr,update(v->l,tl,tm,pos,nval),v->r);
	} else{
		return new node(tl,tr,v->l,update(v->r,tm+1,tr,pos,nval));
	}
}

pi E[MAXN];
map<int,int> D;
map<int,int> R;
void discretize(vector<int> vec){
	vector<int> dis=vec;
	sort(all(dis));
	dis.resize(unique(all(dis))-dis.begin());
	FOR(i,0,vec.size()-1){
		D[vec[i]]=lower_bound(all(dis),vec[i])-dis.begin()+1;
		R[lower_bound(all(dis),vec[i])-dis.begin()+1]=vec[i];
	}
}
vector<pair<node*,node*>> nodes;
void ask(int x, int y) {
	for(;head[x]!=head[y];y=parent[head[y]]){
		if(depth[head[x]]>depth[head[y]])swap(x,y);
		nodes.pb({roots[pos[head[y]]-1],roots[pos[y]]});
	}
	if(x==y)return;
	if(depth[x]>depth[y])swap(x,y);
	db2(pos[x],pos[y]);
	nodes.pb({roots[pos[x]],roots[pos[y]]});
}
int32_t main() 
{
	IAMSPEED
	memset(heavy,-1,sizeof heavy);
	cin >> n >> m >> q;
	FOR(i,1,n-1){
		cin >> E[i].f >> E[i].s;
	}
	vector<int> disc;
	FOR(i,1,m){
		int x; cin >> x;
		int cost; cin>>cost;
		disc.pb(cost);
		V[x].pb(cost);
	}
	discretize(disc);
	FOR(i,1,n-1){
		adj[E[i].f].pb({E[i].s,i}); // this is the edge index
		adj[E[i].s].pb({E[i].f,i}); // this is the edge index
	}
	dfs(1,-1);
	decompose(1,1);
	vector<pi> vec;
	FOR(i,2,n){
		vec.pb({pos[i],i});
	}
	sort(all(vec));
	roots[1]=build(0,n+5);
	for(auto x:vec) {
		roots[x.f]=roots[x.f-1];
		//db(x.s);
		//dbv(W[x.s]);
		for(auto cost:W[x.s]){
			roots[x.f]=update(roots[x.f],0,n+5,D[cost],cost);
		}
		
	}
	while(q--){
		nodes.clear();
		int s,t,x,y; cin >> s >> t >> x >> y;
		ask(s,t);
		for(auto &x:nodes){
			node* lf=x.f;
			node* rg=x.s;
		}
		vector<pair<node*,node*>> V=nodes;
		bool done=0;
		int res=0;
		int val=0;
		int num=0;
		int S,E;
		while(!done){
			
			int lfsum=0;
			int lfnum=0;

			for(auto &x:nodes){
				node* lf=x.f;
				node* rg=x.s;

				S=lf->s;
				E=lf->e;

				if(lf->s==lf->e){
					done=1;
					res=lf->s;
					break;
				}
				lfsum+=rg->l->sum - lf->l->sum;
				lfnum+=rg->l->num - lf->l->num;
			}
			if(val+lfsum<=y){
				val+=lfsum;
				num+=lfnum;

				for(auto &x:nodes){
					x.f=x.f->r;
					x.s=x.s->r;
				}
			} else {
				for(auto &x:nodes){
					x.f=x.f->l;
					x.s=x.s->l;
				}
			}
		}
		//
		// it ended at res. hence, we might be able to get some of res+1 also. 
		--res;
		int extra=0;
		if(R[res+1])extra=(y-val)/R[res+1];
		int ss=num+extra;
		int tot = 0;
		for(auto &x:V){
			node* lf=x.f;
			node* rg=x.s;
			tot+=rg->num-lf->num;
		}
		int spend=tot-ss;
		db2(tot,ss);
		assert(spend>=0);
		if(spend>x){
			cout<<-1<<'\n';
		} else{
			cout<<x-spend<<'\n';
		}
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.cpp:193:10: warning: unused variable 'lf' [-Wunused-variable]
  193 |    node* lf=x.f;
      |          ^~
currencies.cpp:194:10: warning: unused variable 'rg' [-Wunused-variable]
  194 |    node* rg=x.s;
      |          ^~
currencies.cpp:201:7: warning: variable 'S' set but not used [-Wunused-but-set-variable]
  201 |   int S,E;
      |       ^
currencies.cpp:201:9: warning: variable 'E' set but not used [-Wunused-but-set-variable]
  201 |   int S,E;
      |         ^

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