Submission #792492

#	Time	Username	Problem	Language	Result	Execution time	Memory
792492		vjudge1	Two Currencies (JOI23_currencies)	C++17	100 / 100	721 ms	47500 KiB

currencies

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 100100;

using namespace std;

int n, m, q;
int dip[N];
int f[N][20];
int tin[N];
int tout[N];
int tim;
long long F[N], F2[N];

int A[N], B[N];
vector<int> v[N];
pair<int, int> cp[N];
int par[N];

long long s[N], t[N], x[N], y[N];
int tl[N], tr[N];
vector<int> qu[N];
int D[N];

void dfs(int x, int p)
{
    tin[x] = ++tim;
    f[x][0] = p;
    for (int i = 1; i < 20; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i: v[x]) {
        int y = A[i] ^ B[i] ^ x;
        if (y == p) {
            continue;
        }
        dip[y] = dip[x] + 1;
        dfs(y, x);
    }
    tout[x] = tim;
}

bool isp(int x, int y)
{
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
    if (isp(x, y)) {
        return x;
    } else if(isp(y, x)){
        return y;
    }
    for (int i = 19; i >= 0; i--) {
        if (!isp(f[x][i], y)) {
            x = f[x][i];
        }
    }
    return f[x][0];
}

void upd(int x, int y)
{
    while (x < N) {
        F[x] += y;
        x += x & -x;
    }
}

long long get(int x)
{
    long long res = 0;
    while (x > 0) {
        res += F[x];
        x -= x & -x;
    }
    return res;
}

void upd2(int x, int y)
{
    while (x < N) {
        F2[x] += y;
        x += x & -x;
    }
}

long long get2(int x)
{
    long long res = 0;
    while (x > 0) {
        res += F2[x];
        x -= x & -x;
    }
    return res;
}

int main()
{
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(i);
        v[y].push_back(i);

        A[i] = x;
        B[i] = y;
    }

    for (int i = 1; i <= m; i++) {
        cin >> cp[i].se >> cp[i].fi;
    }
    sort(cp + 1, cp + m + 1);

    for (int i = 1; i <= q; i++) {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        tl[i] = 0;
        tr[i] = m;
    }

    dfs(1, 1);
    for (int i = 1; i < n; i++) {
        if (dip[A[i]] > dip[B[i]]) {
            swap(A[i], B[i]);
        }
    }
    for (int i = 1; i <= q; i++) {
        par[i] = lca(s[i], t[i]);
    }

    for (int it = 1; it <= 22; it++) {
        for (int i = 1; i <= q; i++) {
            int tm = (tl[i] + tr[i]) / 2 + (tl[i] < tr[i]);
            //cout << tl[i] << " " << tr[i] << " " << tm << endl;
            if (tl[i] <= tr[i]) {
                qu[tm].push_back(i);
            }
        }
        for (int i = 0; i <= m; i++) {
            if (i > 0) {
                int j = cp[i].se;
                upd(tin[B[j]], cp[i].fi);
                upd(tout[B[j]] + 1, -cp[i].fi);
                upd2(tin[B[j]], 1);
                upd2(tout[B[j]] + 1, -1);
            }
            for (int j: qu[i]) {
                long long tot = get(tin[s[j]]) + get(tin[t[j]]) - 2 * get(tin[par[j]]);
                long long col = get2(tin[s[j]]) + get2(tin[t[j]]) - 2 * get2(tin[par[j]]);
                D[j] = col;
                if (tot <= y[j]) {
                    tl[j] = i;
                } else {
                    tr[j] = i - 1;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            F[i] = F2[i] = 0;
            qu[i].clear();
        }
    }
    for (int i = 1; i <= m; i++) {
        int j = cp[i].se;
        upd2(tin[B[j]], 1);
        upd2(tout[B[j]] + 1, -1);
    }

    for (int i = 1; i <= q; i++) {
        int golds = get2(tin[s[i]]) + get2(tin[t[i]]) - 2 * get2(tin[par[i]]);
        //cout << golds << " " << D[i] << " " << tl[i] << " " << tr[i] << endl;
        golds = x[i] - (golds - D[i]);
        cout << max(golds, -1) << "\n";
    }
}

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