Submission #1004760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004760		pcc	Two Currencies (JOI23_currencies)	C++17	100 / 100	1624 ms	95936 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;
vector<int> tree[mxn];
int par[mxn],link_top[mxn],sz[mxn],bs[mxn],idx[mxn],dep[mxn],cnt;
vector<ll> roads[mxn];
int N,M,Q;
vector<ll> all;
pii edges[mxn];

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	vector<pll> seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			for(auto &i:roads[l])seg[now].push_back(pll(i,0));
		}
		else{
			build(ls,l,mid);
			build(rs,mid+1,r);
			for(int i = 1;i<seg[ls].size();i++)seg[now].push_back(pll(seg[ls][i].fs,0));
			for(int i = 1;i<seg[rs].size();i++)seg[now].push_back(pll(seg[rs][i].fs,0));
		}
		seg[now].push_back(pll(0,0));
		sort(seg[now].begin(),seg[now].end());
		for(int i = 1;i<seg[now].size();i++)seg[now][i].sc = seg[now][i-1].sc+seg[now][i].fs;
		return;
	}
	vector<int> getrange(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r){
			return {now};
		}
		if(mid>=e)return getrange(ls,l,mid,s,e);
		else if(mid<s)return getrange(rs,mid+1,r,s,e);
		else{
			auto tl = getrange(ls,l,mid,s,e);
			auto tr = getrange(rs,mid+1,r,s,e);
			if(tl.size()>tr.size())for(auto &i:tr)tl.push_back(i);
			else for(auto &i:tl)tr.push_back(i);
			return (tl.size()>tr.size()?tl:tr);
		}
	}
#undef ls
#undef rs
#undef mid
};

void dfs1(int now){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par[now])continue;
		par[nxt] = now;
		dep[nxt] = dep[now]+1;
		dfs1(nxt);
		sz[now] += sz[nxt];
		if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
	}
	return;
}

void dfs2(int now,int top){
	link_top[now] = top;
	idx[now] = ++cnt;
	if(bs[now])dfs2(bs[now],top);
	for(auto nxt:tree[now]){
		if(nxt == par[now]||nxt == bs[now])continue;
		dfs2(nxt,nxt);
	}
	return;
}

SEG seg;

vector<int> LCA(int a,int b){
	vector<int> re;
	int ta = link_top[a],tb = link_top[b];
	while(ta != tb){
		if(dep[ta]<dep[tb]){
			swap(a,b);
			swap(ta,tb);
		}
		auto tv = seg.getrange(0,1,N,idx[ta],idx[a]);
		for(auto &i:tv)re.push_back(i);
		a = par[ta];
		ta = link_top[a];
	}
	if(dep[a]>dep[b])swap(a,b);
	if(a != b){
		auto tv = seg.getrange(0,1,N,idx[a]+1,idx[b]);
		for(auto &i:tv)re.push_back(i);
	}
	return re;
}

pll getall(vector<int>& ids,ll lim){
	pll re = pll(0,0);
	for(auto &i:ids){
		auto p = lower_bound(seg.seg[i].begin(),seg.seg[i].end(),pll(lim+1,-1))-seg.seg[i].begin();
		assert(p);
		re.fs += seg.seg[i][p-1].sc;
		re.sc += seg.seg[i].size()-p;
	}
	return re;
}

void solve(int s,int t,ll gold,ll silv){
	vector<int> ids = LCA(s,t);
	int l = 0,r = all.size()-1;
	while(l != r){
		int mid = (l+r+1)>>1;
		if(getall(ids,all[mid]).fs>silv)r = mid-1;
		else l = mid;
	}
	ll ans = -1;
	//cout<<all[l]<<":"<<getall(ids,all[l]).fs<<','<<getall(ids,all[l]).sc<<"\n";
	if(l == all.size()-1)ans = max(ans,gold-getall(ids,all[l]).sc);
	else{
		pll ta = getall(ids,all[l]);
		pll tb = getall(ids,all[l+1]);
		silv -= ta.fs;
		//cout<<all[l]<<' '<<all[l+1]<<','<<ta.fs<<" "<<ta.sc<<','<<tb.fs<<' '<<tb.sc<<'\n';
		gold = max(-1ll,gold-(ta.sc-min(silv/all[l+1],ta.sc-tb.sc)));
		ans = gold;
	}
	cout<<ans<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		edges[i] = pii(a,b);
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	par[1] = 1;
	dfs1(1);
	dfs2(1,1);
	assert(cnt == N);
	for(int i = 0;i<M;i++){
		ll p,val;
		cin>>p>>val;
		all.push_back(val);
		auto &[a,b] = edges[p];
		if(dep[a]>dep[b])swap(a,b);
		assert(dep[b]-dep[a] == 1);
		roads[idx[b]].push_back(val);
	}
	all.push_back(0);
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());
	seg.build(0,1,N);
	while(Q--){
		ll s,t,gold,silv;
		cin>>s>>t>>gold>>silv;
		solve(s,t,gold,silv);
	}
}

Compilation message (stderr)

currencies.cpp: In member function 'void SEG::build(int, int, int)':
currencies.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int i = 1;i<seg[ls].size();i++)seg[now].push_back(pll(seg[ls][i].fs,0));
      |                  ~^~~~~~~~~~~~~~~
currencies.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int i = 1;i<seg[rs].size();i++)seg[now].push_back(pll(seg[rs][i].fs,0));
      |                  ~^~~~~~~~~~~~~~~
currencies.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i = 1;i<seg[now].size();i++)seg[now][i].sc = seg[now][i-1].sc+seg[now][i].fs;
      |                 ~^~~~~~~~~~~~~~~~
currencies.cpp: In function 'void solve(int, int, long long int, long long int)':
currencies.cpp:130:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  if(l == all.size()-1)ans = max(ans,gold-getall(ids,all[l]).sc);
      |     ~~^~~~~~~~~~~~~~~

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