Submission #1126363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126363		Pekiban	Two Currencies (JOI23_currencies)	C++17	0 / 100	7 ms	9032 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back

const int N = 1e5+5 , LOG = 18;
struct EUDQ {
    vector<int> g[N];
    int D[N], up[LOG][N], tin[N], tout[N], n, tm = 0;   
    ll st[4*N], lz[4*N];
    void dfs(int s, int e = -1) {
        tin[s] = ++tm;
        for (auto u : g[s]) {
            if (u == e) continue;
            D[u] = D[s] + 1, up[0][u] = s;
            dfs(u, s);
        }
        tout[s] = tm;
    }
    int jump(int u, int k) {
        for (int i = LOG-1; i >= 0; --i) {
            if ((k >> i) & 1)   u = up[i][u];
        }
        return u;
    }
    void init() {
        dfs(1);
        for (int i = 1; i < LOG; ++i) {
            for (int j = 1; j <= n; ++j) {
                up[i][j] = up[i-1][up[i-1][j]];
            }
        }
    }
    void reset() {
        fill(st, st+4*N, 0);
        fill(lz, lz+4*N, 0);
    }
    int lca(int u, int v) {
        if (D[u] < D[v])    swap(u, v);
        u = jump(u, D[u] - D[v]);
        if (u == v) return u;
        for (int i = LOG-1; i >= 0; --i) {
            if (up[i][u] != up[i][v])   u = up[i][u], v = up[i][v];
        }
        return up[0][u];
    }
    void push(int i) {
        if (lz[i]) {
            lz[2*i] += lz[i];
            lz[2*i+1] += lz[i];
            lz[i] = 0;
        }
    }
    void upd(int l, int r, int x, int i, int l2, int r2) {
        if (l <= l2 && r2 <= r) {
            lz[i] += x;
            return;
        }
        push(i);
        int m2 = (l2 + r2)/2;
        if (l <= m2)    upd(l, r, x, 2*i, l2, m2);
        if (m2+1 <= r)  upd(l, r, x, 2*i+1, m2+1, r2);
        st[i] = st[2*i] + st[2*i+1];
    }
    void add(int u, int v, int x) {
        if (D[u] < D[v])    swap(u, v);
        upd(tin[u], tout[u], x, 1, 1, n);
    }
    ll qry(int p, int i, int l2, int r2) {
        if (l2 == r2)   return lz[i];
        push(i);
        int m2 = (l2 + r2)/2;
        if (p <= m2)    return qry(p, 2*i, l2, m2);
        return qry(p, 2*i+1, m2+1, r2);
    }
    ll qry(int p) {
        return qry(p, 1, 1, n);
    }
    ll calc(int u, int v) {
        return qry(tin[u]) + qry(tin[v]) - 2*qry(tin[lca(u, v)]);
    }
} T;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q; T.n = n;
    array<int, 2> E[n];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        T.g[u].pb(v); T.g[v].pb(u);
        E[i] = {u, v};
    }
    array<int, 2> e[m+1];
    for (int i = 1; i <= m; ++i)    cin >> e[i][1] >> e[i][0];
    sort(e+1, e+m+1);
    for (int i = 1; i <= m; ++i)    swap(e[i][0], e[i][1]);
    array<int, 4> qu[q+1];
    for (int i = 1; i <= q; ++i)    cin >> qu[i][0] >> qu[i][1] >> qu[i][2] >> qu[i][3];
    int L[q+1], R[q+1], P[q+1];
    fill(L, L+q+1, 0); fill(R, R+q+1, m); fill(P, P+q+1, 0);
    T.init();
    // for (int _ = 0; _ < LOG; ++_) {
    //     vector<int> B[m+1];
    //     T.reset();
    //     for (int i = 1; i <= q; ++i) {
    //         if (L[i] <= R[i]) {
    //             B[(L[i] + R[i]) / 2].pb(i);
    //         }
    //     } 
    //     for (int i = 0; i <= m; ++i) {
    //         if (i)  T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
    //         for (auto j : B[i]) {
    //             if (T.calc(qu[j][0], qu[j][1]) <= qu[j][3]) P[j] = i, L[j] = i+1;
    //             else {
    //                 R[j] = i-1;
    //             }
    //         }
    //     }
    // }
    for (int i = 1; i <= m; ++i) {
        T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
        for (int j = 1; j <= q; ++j) {
            if (T.calc(qu[j][0], qu[j][1]) <= qu[j][3]) P[j] = i;
        }
    }
    T.reset();
    vector<int> B[m+1];
    for (int i = 1; i <= q; ++i)    B[P[i]].pb(i);
    for (int i = 0; i <= m; ++i) {
        if (i)  T.add(E[e[i][0]][0], E[e[i][0]][1], 1);
        for (auto j : B[i]) {
            qu[j][2] += T.calc(qu[j][0], qu[j][1]);
        }
    }
    for (int i = 1; i <= q; ++i) {
        cout << max(-1LL, qu[i][2] - T.calc(qu[i][0], qu[i][1])) << '\n';
    }
}

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