Submission #1123729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123729		Pwo	Two Currencies (JOI23_currencies)	C++17	28 / 100	167 ms	31668 KiB

currencies

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

int n, m, q, c, t = 1;
pair<int, int> a[100005];
int w[100005];
vector<pair<int, int>> g[100005];
int dist[100005], tin[100005], tout[100005];
int up[100005][18];

void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = t++;
	for (int i = 1; i < 18; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (const auto [u, x] : g[v]) {
		if (u != p) {
			dist[u] = dist[v] + x;
			dfs(u, v);
		}
	}
	tout[v] = t++;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 17; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

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++) cin >> a[i].first >> a[i].second;
	for (int i = 0; i < m; i++) {
		int p; cin >> p >> c;
		w[p]++;
	}
	for (int i = 1; i < n; i++) {
		g[a[i].first].emplace_back(a[i].second, w[i]);
		g[a[i].second].emplace_back(a[i].first, w[i]);
	}
	
	dfs(1, 1);
	
	while (q--) {
		int s, t, x, y; cin >> s >> t >> x >> y;
		y /= c;
		int z = lca(s, t);
		int d = dist[s] + dist[t] - dist[z] * 2;

		if (d > x + y) cout << -1 << '\n';
		else if (y > d) cout << x << '\n';
		else cout << x - d + y << '\n';
	}
}

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