Submission #888628

#	Time	Username	Problem	Language	Result	Execution time	Memory
888628		vjudge1	Two Currencies (JOI23_currencies)	C++17	10 / 100	5054 ms	29512 KiB

currencies

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 100005;
vi g[N];
pii p[N];
map<pii, vi> mp;
int t;
int pre[N];
void dfs(int pos, int pr){
	if(pos == t)return;
	for(auto to:g[pos]){
		if(to!=pr){
			pre[to] = pos;
			dfs(to, pos);
		}
	}
}
void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	vii cui;
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
		cui.pb({a, b});
	}
	for(int i = 0; i < m; i++){
		int j, c;
		cin >> j >> c;j--;
		mp[cui[j]].pb(c);
		mp[{cui[j].ss, cui[j].ff}].pb(c);
	}
	if(n >= 2006){
		dfs(1, -1);
		vi pas;
		while(q--){
			int s, x, y;
			cin >> s >> t >> x >> y;
			if(s > t)swap(s, t);
			int r = t;
			while(r!=s){
				for(auto i:mp[{r, pre[r]}])pas.pb(i);
				r = pre[r];
			}
			sort(all(pas));
			for(auto i:pas){
				if(i <= y)y -= i;
				else x--;
			}pas.clear();
			cout << (x<0?-1:x) << '\n';
		}
	}else{
		vi pas;
		while(q--){
			int s, x, y;
			cin >> s >> t >> x >> y;
			dfs(s, -1);
			int r = t;
			while(r!=s){
				for(auto i:mp[{r, pre[r]}])pas.pb(i);
				r = pre[r];
			}
			sort(all(pas));
			for(auto i:pas){
				if(i <= y)y -= i;
				else x--;
			}pas.clear();
			cout << (x<0?-1:x) << '\n';
		}
	}
	
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

currencies.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~

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