Submission #888684

#TimeUsernameProblemLanguageResultExecution timeMemory
888684vjudge1Two Currencies (JOI23_currencies)C++17
10 / 100
1817 ms33128 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;
using namespace __gnu_pbds;

const int mod = 998244353;
const long double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1e5 + 5;

void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	if(n <= 2000 && m <= 2000 && q <= 2000){
		vector<int> u(n+1),v(n+1);
		vector<vector<int> > g(n+1);
		for(int i = 1; i < n; i++){
			cin >> u[i] >> v[i];
			g[u[i]].pb(v[i]);
			g[v[i]].pb(u[i]);
		}
		map<pair<int,int>,vector<int> > dis;
		for(int i = 0; i < m; i++){
			int a,b;
			cin >> a >> b;
			dis[{u[a],v[a]}].pb(b);
			dis[{v[a],u[a]}].pb(b);
		}
		
		vector<int> ansv;
		int s,t,x,y;
		function<void(int,int,vector<int>)> dfs = [&](int w,int p,vector<int> us){
			for(auto i : dis[{p,w}]){
				us.pb(i);
			}
			if(w == t){
				ansv = us;
				return;
			}
			for(int to : g[w]){
				if(to != p){
					dfs(to,w,us);
				}
			}
		};
		
		while(q--){
			cin >> s >> t >> x >> y;
			dfs(s,0,{});
			sort(all(ansv));
			for(int i : ansv){
				if(i > y) x--;
				else y -= i;
			}
			if(x >= 0) cout << x << '\n';
			else cout << "-1\n";
		}
	}
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message (stderr)

currencies.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...