Submission #1123728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123728		Pwo	Two Currencies (JOI23_currencies)	C++17	10 / 100	231 ms	95172 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q; 
pair<int, int> a[2005];
vector<int> g[2005];
int par[2005];
vector<int> z[2005][2005];

void dfs(int v, int p) {
	par[v] = p;
	for (const int u : g[v]) {
		if (u != p) dfs(u, v);
	}
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		a[i] = {u, v};
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < m; i++) {
		int p, c; cin >> p >> c;
		z[a[p].first][a[p].second].push_back(c);
		z[a[p].second][a[p].first].push_back(c);
	}
	
	while (q--) {
		int s, t, x, y; cin >> s >> t >> x >> y;
		dfs(s, -1);
		vector<int> costs;
		int cur = t, prev = -1;
		while (cur != -1) {
			if (prev != -1) {
				for (const int u : z[cur][prev])
					costs.push_back(u);
			}
			prev = cur;
			cur = par[cur];
		}
		sort(costs.begin(), costs.end());
		for (const int u : costs) {
			if (y >= u) y -= u;
			else x--;
		}
		if (x < 0) cout << -1 << '\n';
		else cout << x << '\n';
	}
}

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