Submission #1369180

#TimeUsernameProblemLanguageResultExecution timeMemory
1369180tranvinhhuy2010Two Currencies (JOI23_currencies)C++20
100 / 100
1144 ms41720 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct checkpoint {
    int p;
    ll c;

    bool operator < (const checkpoint& oth) const {
        return c < oth.c;
    }
};

const int nmax = 1e5 + 5, lg = 17;
int n, m, q, s[nmax], t[nmax], d[nmax], up[nmax][20], in[nmax], out[nmax], timer, l[nmax], r[nmax], ans[nmax];
checkpoint cp[nmax];
ll x[nmax], y[nmax], bit[nmax], cnt[nmax], total[nmax];
vector <int> g[nmax], bucket[nmax];
pair <int, int> e[nmax];

void dfs(int u) {
    in[u] = ++timer;

    for (int v : g[u]) {
        if (v==up[u][0]) continue;

        d[v] = d[u] + 1;
        up[v][0] = u;
        for (int j=1; j<=lg; j++)
            up[v][j] = up[up[v][j-1]][j-1];

        dfs(v);
    }

    out[u] = timer;
}

int lca(int u, int v) {
    if (d[u]<d[v]) swap(u, v);
    int dif = d[u] - d[v];
    for (int j=0; j<=lg; j++)
        if (dif >> j & 1) u = up[u][j];

    if (u==v) return u;

    for (int j=lg; j>=0; j--) {
        if (up[u][j]!=up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }

    return up[u][0];
}

void update(int i, ll x, ll bit[]) {
    while (i<=n) {
        bit[i] += x;
        i += i & -i;
    }
}

ll get(int i, ll bit[]) {
    ll sum = 0;
    while (i>0) {
        sum += bit[i];
        i -= i & -i;
    }

    return sum;
}

void range(int l, int r, ll x, ll bit[]) {
    update(l, x, bit);
    update(r + 1, -x, bit);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (int i=1; i<n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        e[i] = {u, v};
    }
    for (int i=1; i<=m; i++)
        cin >> cp[i].p >> cp[i].c;
    for (int i=1; i<=q; i++)
        cin >> s[i] >> t[i] >> x[i] >> y[i];

    dfs(1);
    sort(cp + 1, cp + 1 + m);

    for (int i=1; i<=q; i++) {
        l[i] = 0;
        r[i] = m;
    }

    bool change = true;
    while (change) {
        change = false;
        int mx = 0;
        for (int i=1; i<=q; i++) {
            if (l[i]>r[i]) continue;
            int mid = (l[i] + r[i]) / 2;
            bucket[mid].push_back(i);
            mx = max(mx, mid);
            change = true;
        }

        if (!change) break;

        for (int mid=0; mid<=m; mid++) {
            if (mid>0) {
                int u = e[cp[mid].p].first;
                if (d[e[cp[mid].p].second]>d[u]) u = e[cp[mid].p].second;
                range(in[u], out[u], cp[mid].c, bit);
                range(in[u], out[u], 1, cnt);
            }

            for (int i : bucket[mid]) {
                ll sum = get(in[s[i]], bit) + get(in[t[i]], bit) - 2 * get(in[lca(s[i], t[i])], bit);
                if (sum<=y[i]) {
                    total[i] = get(in[s[i]], cnt) + get(in[t[i]], cnt) - 2 * get(in[lca(s[i], t[i])], cnt);
                    l[i] = mid + 1;
                }
                else r[i] = mid - 1;
            }
        }

        for (int i=0; i<=m; i++)
            bucket[i].clear();
        for (int i=1; i<=n; i++)
            bit[i] = cnt[i] = 0;
    }

    for (int i=1; i<=m; i++) {
        int u = e[cp[i].p].first;
        if (d[e[cp[i].p].second]>d[u]) u = e[cp[i].p].second;
        range(in[u], out[u], 1, cnt);
    }

    for (int i=1; i<=q; i++) {
        ll adu = get(in[s[i]], cnt) + get(in[t[i]], cnt) - 2 * get(in[lca(s[i], t[i])], cnt);
        if (x[i]>=adu-total[i]) cout << x[i] + total[i] - adu << '\n';
        else cout << "-1\n";
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...