Submission #851578

#	Time	Username	Problem	Language	Result	Execution time	Memory
851578		willychan	Two Currencies (JOI23_currencies)	C++14	0 / 100	2 ms	6236 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int N = 1e5+5;
vector<pair<int,int> > side[N];
vector<pair<int,int> > edgeset;

pair<int,int> father[N][20];
int dep[N];
void dfs(int c){
	for(auto i : side[c]){
		if(father[i.first][0].first==0) {
			dep[i.first] = dep[c]+1;
			father[i.first][0] = {c,i.second};
			dfs(i.first);
		}
	}
}

int get(int a,int b){
	if(a==b) return 0;
	ll sum =0;
	if(dep[a]>dep[b]) swap(a,b);
	if(dep[b]>dep[a]){
		for(int j=19;j>=0;j--){
			if(dep[father[b][j].first]>dep[a]){
				sum+=father[b][j].second;
				b = father[b][j].first;
			}
			
		}
		sum+=father[b][0].second;
		b = father[b][0].first;
	}
	assert(dep[a]==dep[b]);
	if(a==b) return sum;
	for(int j=19;j>=0;j--){
		if(father[a][j].first!=father[b][j].first){
			sum+=father[a][j].second;
			sum+=father[b][j].second;
			a=father[a][j].first;
			b=father[b][j].first;
		}
	}
	sum+=father[a][0].second;
	sum+=father[b][0].second;
	return sum;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m,q;cin>>n>>m>>q;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		side[a].push_back({b,0});
		side[b].push_back({a,0});
		edgeset.push_back({a,side[a].size()-1});
		edgeset.push_back({b,side[b].size()-1});
	}
	int C;
	for(int i=0;i<m;i++){
		int p;cin>>p>>C;
		p--;
		pair<int,int> ff=edgeset[2*p];
		pair<int,int> ss=edgeset[2*p+1];
		side[ff.first][ff.second].second++;
		side[ss.first][ss.second].second++;
	}
	for(int i=1;i<20;i++) father[1][i] ={1,0};
	dfs(1);
	for(int j=1;j<20;j++){
		for(int i=2;i<=n;i++){
			int v = father[i][j-1].second+father[father[i][j-1].first][j-1].second;
			father[i][j] = {father[father[i][j-1].first][j-1].first,v};
		}
	}
	while(q--){
		int a,b,x,y;cin>>a>>b>>x>>y;
		int cnt = 0;
		while(a!=b){
			if(dep[a]>dep[b]) swap(a,b);
			cnt+=father[b][0].second;
			b = father[b][0].first;
		}
		int c = y/C;
		int howmany = max(0,cnt-c);
		if(x<howmany) cout<<-1<<"\n";
		else cout<<x-howmany<<"\n";
	}
	return 0;
}

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