Submission #826895

#	Time	Username	Problem	Language	Result	Execution time	Memory
826895		khshg	Two Currencies (JOI23_currencies)	C++14	10 / 100	5058 ms	37660 KiB

currencies

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

const int LG = 20;
int N, M, Q;
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> adj;
vector<array<int, LG>> par;
vector<int> lvl;
vector<vector<int>> pp;

void dfs(int s) {
	for(auto& v : adj[s]) {
		int u = v.first;
		if(u == par[s][0]) continue;
		lvl[u] = lvl[s] + 1;
		par[u][0] = s;
		for(int i = 1; i < LG; ++i) {
			par[u][i] = par[par[u][i - 1]][i - 1];
		}
		dfs(u);
	}
}

int lca(int s, int t) {
	if(lvl[t] > lvl[s]) swap(s, t);
	for(int i = LG - 1; i >= 0; --i) {
		if(lvl[par[s][i]] >= lvl[t]) {
			s = par[s][i];
		}
	}
	if(s == t) return s;
	for(int i = LG - 1; i >= 0; --i) {
		if(par[s][i] != par[t][i]) {
			s = par[s][i];
			t = par[t][i];
		}
	}
	return par[s][0];
}
 
int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> M >>  Q;
	adj.resize(N);
	for(int i = 1; i < N; ++i) {
		int u, v; cin >> u >> v;
		--u; --v;
		e.emplace_back(u, v);
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	lvl.resize(N);
	par.resize(N);
	dfs(0);
	for(int i = 0; i + 1 < N; ++i) {
		if(par[e[i].second][0] == e[i].first) {
			swap(e[i].first, e[i].second);
		}
	}
	pp.resize(N);
	for(int i = 0; i < M; ++i) {
		int p, c; cin >> p >> c;
		--p;
		pp[e[p].first].push_back(c);
	}
	while(Q--) {
		int S, T, X;
		long long Y;
		cin >> S >> T >> X >> Y;
		--S; --T;
		int L = lca(S, T);
		vector<int> cur;
		while(S != L) {
			for(auto& u : pp[S]) {
				cur.push_back(u);
			}
			S = par[S][0];
		}
		while(T != L) {
			for(auto& u : pp[T]) {
				cur.push_back(u);
			}
			T = par[T][0];
		}
		sort(begin(cur), end(cur));
		int ans = X;
		for(int i = 0; i < (int)cur.size(); ++i) {
			if(Y - cur[i] >= 0) {
				Y -= cur[i];
			} else {
				ans = X - ((int)cur.size() - i);
				break;
			}
		}
		if(ans < 0) {
			cout << "-1\n";
		} else {
			cout << ans << '\n';
		}
	}
	return 0;
}

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