Submission #1261559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261559		4QT0R	Two Currencies (JOI23_currencies)	C++20	10 / 100	5088 ms	22028 KiB

currencies

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

vector<pair<ll, ll>> graph[100002];
vector<ll> bramki[100002];

ll dep[100002];
pair<ll, ll> par[100002];

void dfs(ll v, ll p)
{
	for (auto [u, ind] : graph[v])
	{
		if (u == p)
			continue;
		par[u] = {v, ind};
		dep[u] = dep[v] + 1;
		dfs(u, v);
	}
}

ll zap(ll v, ll u, ll x, ll y)
{
	vector<ll> costs;
	if (dep[v] > dep[u])
		swap(v, u);
	while (dep[v] < dep[u])
	{
		for (auto x : bramki[par[u].second])
			costs.push_back(x);
		u = par[u].first;
	}
	while (v != u)
	{
		for (auto x : bramki[par[u].second])
			costs.push_back(x);
		for (auto x : bramki[par[v].second])
			costs.push_back(x);
		v = par[v].first;
		u = par[u].first;
	}
	sort(costs.begin(),costs.end(),greater<ll>());
	while(costs.size() && y>=costs.back()){
		y-=costs.back();
		costs.pop_back();
	}
	if (x < (ll)costs.size())return -1;
	else return x - costs.size();
}

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

	ll n, m, q;
	cin >> n >> m >> q;
	for (ll i = 1, a, b; i < n; i++)
	{
		cin >> a >> b;
		graph[a].push_back({b, i});
		graph[b].push_back({a, i});
	}
	for (ll i = 1, p, c; i <= m; i++)
	{
		cin >> p >> c;
		bramki[p].push_back(c);
	}
	dfs(1, 0);
	for (ll i = 1, a, b, x, y; i <= q; i++)
	{
		cin >> a >> b >> x >> y;
		cout << zap(a, b, x, y) << '\n';
	}
}

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