Submission #1126312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126312		Pekiban	Two Currencies (JOI23_currencies)	C++17	0 / 100	125 ms	110404 KiB

currencies

#include <bits/stdc++.h>

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

const int N = 8e5 + 5, LOG = 20;
struct HLD {
    vector<int> g[N];
    int D[N], up[LOG][N], sz[N], pr[N], id[N], C = 0;
    ll a[N];
    struct BIT {
        int n;
        vector<ll> b;
        void init(int _n) {
            if (n > _n) return;
            b.resize(_n+4, 0);
            n = _n+4;
        }
        void reset() {
            fill(b.begin(), b.end(), 0);
        }
        void add(int p, int x) {
            for (; p < n; p |= (p + 1)) b[p] += x;
        }
        ll sum(int r) {
            ll S = 0;
            for (; r >= 0; r = (r & (r + 1)) - 1)   S += b[r];
            return S;
        }
        ll sum(int l, int r) {
            return sum(r) - (l > 0 ? sum(l-1) : 0);
        }
    } ch[N];
    void dfs(int s, int e = -1) {
        sz[s] = 1;
        for (auto u : g[s]) {
            if (u == e) continue;
            D[u] = D[s] + 1, up[0][u] = s;
            dfs(u, s);
            sz[s] += sz[u];
        }
        for (auto u : g[s]) {
            if (u == e) continue;
            if (sz[u] > sz[s] / 2)  pr[id[u]] = s, id[s] = id[u];
        }
        if (!id[s]) {
            id[s] = ++C;
            pr[id[s]] = s;
        }
    }
    void dfs2(int s, int e = -1) {
        if (e != -1 && id[s] != id[e])    ch[id[e]].init(D[e] - D[pr[id[e]]] + 1);
        if (e != -1 && g[s].size() == 1)    ch[id[s]].init(D[s] - D[pr[id[s]]] + 1);
        for (auto u : g[s]) {
            if (u == e) continue;
            dfs2(u, s);
        }
    }
    void init() {
        dfs(1);
        dfs2(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() {
        for (int i = 0; i < N; ++i) ch[i].reset();
        fill(a, a+N, 0);
    }
    int jump(int u, int k) {
        for (int i = LOG-1; i >= 0; --i) {
            if ((k >> i) & 1)   u = up[i][u];
        }
        return u;
    }
    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 add(int u, int v, ll x) {
        if (D[u] < D[v])    swap(u, v);
        if (id[u] != id[v]) a[u] += x;
        else {
            ch[id[u]].add(D[u] - D[pr[id[u]]], x);
        }
    }
    ll sum(int u, int v) {
        ll S = 0;
        while (D[u] > D[v]) {
            if (id[u] == id[v]) S += ch[id[u]].sum(D[v] - D[pr[id[u]]] + 1, D[u] - D[pr[id[u]]]);
            else {
                S += ch[id[u]].sum(0, D[u] - D[pr[id[u]]]);
            }
            u = pr[id[u]]; if (D[u] <= D[v])    break; 
            S += a[u]; u = up[0][u];
        }
        return S;
    }
    ll calc(int u, int v) {
        int L = lca(u, v);
        if (D[u] < D[v])    swap(u, v);
        return sum(u, L) + sum(v, L);
    }
} T;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    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 i = 1; i <= m; ++i) {
    //     cout << E[e[i][0]][0] << ' ' << E[e[i][0]][1] << ' ' << e[i][1] << '\n';
    //     T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
    //     cout << T.calc(qu[1][0], qu[1][1]) << '\n';
    // }
    
    
    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;
                }
            }
        }
    }
    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