Submission #1281885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281885		muhammad-ahmad	Two Currencies (JOI23_currencies)	C++20	10 / 100	251 ms	992 KiB

currencies

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
using namespace std;

#define int long long
#define endl "\n"

const int N = 2e3 + 5;
vector<int> adj[N];
map<pair<int, int>, int> edge;
vector<int> E[N];
int par[N];

void dfs(int u, int p){
	par[u] = p;
	for (auto v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
	}
	
}

void solve() {
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		edge[{u, v}] = i;
		edge[{v, u}] = i;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	for (int i = 1; i <= m; i++){
		int p, c; cin >> p >> c;
		E[p].push_back(c);
	}
	
	for (int Q = 1; Q <= q; Q++){
		int u, v, g, s;
		cin >> u >> v >> g >> s;
		dfs(u, 0);
		int x = v;
		vector<int> cost;
		while (x != u){
			for (auto j : E[edge[{x, par[x]}]]) cost.push_back(j);
			x = par[x];
		}
		sort(cost.begin(), cost.end());
		int use = cost.size();
		for (auto i : cost){
			if (s - i >= 0){
				s -= i;
				use--;
			}
		}
		if (use > g) cout << -1 << endl;
		else cout << g - use << endl;
	}
	
    return;
}

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);	
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << setprecision(9);
    srand(time(0));

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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