Submission #1243803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243803		Double_Slash	Two Currencies (JOI23_currencies)	C++20	100 / 100	1449 ms	40708 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

int n, m, q, dep[100001], S[100001], E[100001], st[200000][18], def[100001], s[100000], t[100000], x[100000], lca[100000], ans[100000], cnt[100000];
ll y[100000], sum[100000];
vector<int> adj[100001];
vector<pint> c;

template <class T>
struct St {
    int n;
    vector<T> st;

    St(int n) : n(n), st(n << 1) {}

    void upd(int l, int r, const T &v) {
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) st[l++] += v;
            if (r & 1) st[--r] += v;
        }
    }

    T operator()(int i) {
        T ret = 0;
        for (i += n; i; i >>= 1) ret += st[i];
        return ret;
    }
};

void dfs(int i, int p = 0) {
    st[S[i]][0] = i;
    for (int j: adj[i]) {
        if (j == p) continue;
        dep[j] = dep[i] + 1;
        S[j] = E[j] = E[i] + 1;
        dfs(j, i);
        st[E[i] = E[j] + 1][0] = i;
    }
}

void dfs2(int i, int p = 0) {
    for (int j: adj[i]) {
        if (j == p) continue;
        def[j] += def[i];
        dfs2(j, i);
    }
}

template <bool silver, class T>
void calc(int ans[], T cur[]) {
    vector<pint> v = c;
    for (int i = q; i--;) v.emplace_back(ans[i], i);
    sort(all(v));
    St<T> st{E[1] + 1};
    for (auto &[a, i]: v) {
        if (i < 0) {
            if constexpr (silver) st.upd(S[-i], E[-i] + 1, a);
            else st.upd(S[-i], E[-i] + 1, 1);
        } else cur[i] = st(S[s[i]]) + st(S[t[i]]) - st(S[lca[i]]) * 2;
    }
}

int main() {
    cin >> n >> m >> q;
    pint edges[n - 1];
    for (auto &[a, b]: edges) {
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1);
    auto mn = [&] (int i, int j) { return dep[i] < dep[j] ? i : j; };
    c.resize(m);
    for (auto &[ci, i]: c) {
        cin >> i;
        if (dep[edges[i - 1].first] > dep[edges[i - 1].second]) swap(edges[i - 1].first, edges[i - 1].second);
        ++def[i = edges[i - 1].second];
        cin >> ci;
        i *= -1;
    }
    dfs2(1);
    for (int j = 1; j < 18; ++j) {
        for (int i = 0; i + (1 << j) - 1 <= E[1]; ++i) st[i][j] = mn(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
    auto __lg = [] (int x) { return (int) log2(x); };
    for (int i = q; i--;) {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        int l = min(S[s[i]], S[t[i]]);
        int r = max(E[s[i]], E[t[i]]);
        int j = __lg(r - l + 1);
        lca[i] = mn(st[l][j], st[r - (1 << j) + 1][j]);
    }
    for (int k = 30; k--;) {
        for (int i = q; i--;) ans[i] += 1 << k;
        calc<true>(ans, sum);
        for (int i = q; i--;) {
            if (sum[i] > y[i]) ans[i] -= 1 << k;
        }
    }
    calc<false>(ans, cnt);
    calc<true>(ans, sum);
    for (int i = q; i--;) {
        y[i] -= sum[i];
        cnt[i] = max(0ll, def[s[i]] + def[t[i]] - def[lca[i]] * 2 - cnt[i] - y[i] / (ans[i] + 1));
        if (cnt[i] > x[i]) cout << "-1\n";
        else cout << x[i] - cnt[i] << '\n';
    }
}

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