Submission #743371

#	Time	Username	Problem	Language	Result	Execution time	Memory
743371		emptypringlescan	Two Currencies (JOI23_currencies)	C++17	10 / 100	5050 ms	33332 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200005];
long long cost[200005];
int par[200005],d[200005];
void dfs(int x, int p){
	for(int i:adj[x]){
		if(i==p) continue;
		par[i]=x;
		d[i]=d[x]+1;
		dfs(i,x);
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int> > edges;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		edges.push_back({a,b});
	}
	int cnt=n+1;
	for(int i=0; i<m; i++){
		int a;
		long long b;
		cin >> a >> b;
		cost[cnt]=b;
		edges.push_back({cnt,edges[a-1].second});
		edges[a-1].second=cnt;
		cnt++;
	}
	for(auto i:edges){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	dfs(1,-1);
	for(int i=0; i<q; i++){
		int a,b;
		long long cc,dd;
		cin >> a >> b >> cc >> dd;
		vector<long long> lol;
		while(a!=b){
			if(d[a]<d[b]) swap(a,b);
			lol.push_back(cost[a]);
			a=par[a];
		}
		lol.push_back(cost[a]);
		sort(lol.begin(),lol.end());
		cnt=0;
		for(long long j:lol){
			if(dd<j) break;
			dd-=j;
			cnt++;
		}
		if((cc-((int)lol.size()-cnt))<0) cout << -1 << '\n';
		else cout << cc-(lol.size()-cnt) << '\n';
	}
}

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