Submission #826945

#	Time	Username	Problem	Language	Result	Execution time	Memory
826945		khshg	Two Currencies (JOI23_currencies)	C++14	28 / 100	310 ms	39868 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, pp, cnt;

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];
}

void dfs0(int s) {
	for(auto& v : adj[s]) {
		int u = v.first;
		if(u == par[s][0]) continue;
		cnt[u] = cnt[s] + pp[u];
		dfs0(u);
	}
}
 
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);
	int c;
	for(int i = 0; i < M; ++i) {
		int p; cin >> p >> c;
		--p;
		++pp[e[p].first];
	}
	cnt.resize(N);
	dfs0(0);
	while(Q--) {
		int S, T, X;
		long long Y;
		cin >> S >> T >> X >> Y;
		--S; --T;
		int L = lca(S, T);
		int many = max(0LL, cnt[S] + cnt[T] - 2 * cnt[L] - Y / c);
		int ans = X - many;
		if(ans < 0) {
			cout << "-1\n";
		} else {
			cout << ans << '\n';
		}
	}
	return 0;
}

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