제출 #899145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899145		The_Samurai	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	604 KiB

currencies

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<pair<int, ll>>> g(n + 1);
    vector<pair<int, int>> adj(n - 1);
    vector<ll> val(n - 1);
    for (auto &[x, y]: adj) cin >> x >> y;
    bool sub2 = true;
    ll last = 0;
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        val[p - 1] += c;
        if (i > 0) sub2 &= last == c;
        last = c;
    }
    for (int i = 0; i < n - 1; i++) {
        g[adj[i].first].emplace_back(adj[i].second, val[i]);
        g[adj[i].second].emplace_back(adj[i].first, val[i]);
    }
    if (sub2) {
        const int lg = 17;
        vector jump(lg, vector(n + 1, 0));
        vector<int> tin(n + 1), tout(n + 1), height(n + 1);
        vector<ll> need(n + 1);
        int z = 0;
        auto dfs = [&](auto &dfs, int u, int p) -> void {
            for (int h = 1; h < lg and p != 0; h++) {
                jump[h][u] = jump[h - 1][jump[h - 1][u]];
                if (!jump[h][u]) break;
            }
            tin[u] = z++;
            for (auto [v, c]: g[u]) {
                if (p == v) continue;
                need[v] = need[u] + c / last;
                height[v] = height[u] + 1;
                dfs(dfs, v, u);
            }
            tout[u] = z++;
        };
        dfs(dfs, 1, 0);
        auto isPar = [&](int u, int v) -> bool {
            return tin[u] <= tin[v] and tout[v] <= tout[u];
        };
        auto lca = [&](int u, int v) -> int {
            if (isPar(u, v)) return u;
            if (isPar(v, u)) return v;
            for (int i = lg - 1; i >= 0; i--) {
                if (!jump[i][u] or isPar(jump[i][u], v)) continue;
                u = jump[i][u];
            }
            return jump[0][u];
        };
        while (q--) {
            int u, v;
            ll x, y;
            cin >> u >> v >> x >> y;
            int lc = lca(u, v);
            ll dist = need[u] + need[v] - 2 * need[lc];
            dist -= y / last;
            cout << (x >= dist ? x - max(0ll, dist) : -1) << '\n';
        }
        return;
    }
    assert(false);


}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

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