oj.uz

Submission #899145

# Submission time Handle Problem Language Result Execution time Memory
899145 2024-01-05T14:09:18 Z The_Samurai Two Currencies (JOI23_currencies) C++17
0 / 100
 2 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -