Submission #888719

#	Time	Username	Problem	Language	Result	Execution time	Memory
888719		vjudge1	Two Currencies (JOI23_currencies)	C++17	10 / 100	267 ms	48580 KiB

currencies

#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);
		}
		
		int s,t,x,y;
		vector<int> pr(n+1);
		function<void(int,int)> dfs = [&](int w,int p){
			pr[w] = p;
			for(int to : g[w]){
				if(to != p){
					dfs(to,w);
				}
			}
		};
		
		while(q--){
			cin >> s >> t >> x >> y;
			dfs(s,0);
			vector<int> ansv;
			while(t != s){
				for(int i : dis[{t,pr[t]}]) ansv.pb(i);
				t = pr[t];
			}
			sort(all(ansv));
			for(int i : ansv){
				if(i > y) x--;
				else y -= i;
			}
			if(x >= 0) cout << x << '\n';
			else cout << "-1\n";
		}
	}else{
		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>,int> dis;
		int us;
		for(int i = 0; i < m; i++){
			int a,b;
			cin >> a >> b;
			us = b;
			dis[{u[a],v[a]}] += b;
			dis[{v[a],u[a]}] += b;
		}
		
		vector<int> dist(n+1),tin(n+1),tout(n+1);
		vector<vector<int> > up(20,vector<int>(n+1));
		int timer = 0;
		
		function<void(int, int, int)> dfs = [&](int w, int pr, int d) {
			dist[w] = d;
			tin[w] = ++timer;
			up[0][w] = pr;
			for (int i = 1; i <= 17; i++) {
				up[i][w] = up[i - 1][up[i - 1][w]];
			}
			for (int to : g[w]) {
				if (to != pr) dfs(to, w, d + dis[{w,to}]);
			}
			tout[w] = timer;
		};
		 
		function<bool(int,int)> upper = [&](int a, int b) {
			return tin[a] <= tin[b] && tout[a] >= tout[b];
		};
		 
		function<int(int,int)> lca = [&](int a, int b) {
			if (upper(a, b)) return a;
			if (upper(b, a)) return b;
			for (int i = 17; i >= 0; i--) {
				if (!upper(up[i][a], b)) {
					a = up[i][a];
				}
			}
			return up[0][a];
		};
		
		dfs(1,0,0);
		
		while(q--){
			int s,t,x,y;
			cin >> s >> t >> x >> y;
			int cost = dist[s] + dist[t] - dist[ lca(s,t) ] * 2;
			cost /= us;
			cost -= y / us;
			x -= max(0ll,cost);
			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:134:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  134 | main(){
      | ^~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:125:14: warning: 'us' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |    cost -= y / us;
      |            ~~^~~~

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