Submission #883599

#	Time	Username	Problem	Language	Result	Execution time	Memory
883599		vjudge1	Two Currencies (JOI23_currencies)	C++17	100 / 100	4492 ms	56652 KiB

currencies

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")

#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define int ll
using namespace std;
using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

template<class T>
struct AIB {
    int n;
    vector<T> V;

    AIB(int N) : n(N + 1), V(N + 1) {}

    void update(int p, T v) {
        ++p;
        while(p < n) {
            V[p] += v;
            p += p & -p;
        }
    }

    T query(int p) {
        ++p;
        T re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }
};

struct tree {
    int n;
    vi par, niv, in, out;
    vector<vector<pair<int, ll> > > L;
    vector<vi> Anc;

    AIB<int> NR;
    AIB<ll> COST;

    tree(int N) : n(N), L(N), par(N), niv(N), in(N),
        out(N), NR(2 * N), COST(2 * N) {}

    void add_edge(int u, int v, ll w) {
        L[u].push_back({v, w});
        L[v].push_back({u, w});
    }

    void init() {
        function<void(int, int, int)> dfs = [&](int u, int p, int li) {
            static int tmr = 0;
            niv[u] = li; 
            in[u] = tmr++;
            par[u] = p;
            for(auto [it, w] : L[u]) {
                if(it != p) {
                    dfs(it, u, li + 1);
                }
            }
            out[u] = tmr++;
        };
        dfs(0, -1, 0);
        Anc.push_back(par);
        for(int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(vi(n, -1));
            for(int i = 0; i < n; ++i) {
                Anc[k][i] = Anc[k-1][i] == -1 ? -1 : Anc[k-1][Anc[k-1][i]];
            }
        }
    }

    int lift(int u, int nr) {
        for(int i = 0; i < (int)sz(Anc); ++i) {
            if(nr & (1 << i))
                u = Anc[i][u];
        }
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int i = int(sz(Anc)) - 1; i >= 0; --i) {
            if(Anc[i][u] != Anc[i][v]) {
                u = Anc[i][u];
                v = Anc[i][v];
            }
        }
        return par[u];
    }

    int dist(int u, int v) { return niv[u] + niv[v] - 2 * niv[lca(u, v)]; }

    void enable(int u, int v, ll w) {
        if(niv[u] > niv[v]) swap(u, v);
        NR.update(in[v], 1);
        NR.update(out[v], -1);
        COST.update(in[v], w);
        COST.update(out[v], -w);
    }

    void disable(int u, int v, ll w) {
        if(niv[u] > niv[v]) swap(u, v);
        NR.update(in[v], -1);
        NR.update(out[v], 1);
        COST.update(in[v], -w);
        COST.update(out[v], w);
    }
    
    pair<ll, int> query(int u, int v) {
        int l = lca(u, v);
        int nr = NR.query(in[u]) + NR.query(in[v]) - 2 * NR.query(in[l]);
        ll re = COST.query(in[u]) + COST.query(in[v]) - 2 * COST.query(in[l]);
        return {re, nr};
    }
};

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, ll> > E;
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        E.push_back({u, v, 0});
    }
    vector<pair<int, ll> > P;
    for(int i = 0; i < m; ++i) {
        int p, c;
        cin >> p >> c;
        P.emplace_back(p, c);
    }
    tree Tr(n);
    for(auto [u, v, w] : E) {
        Tr.add_edge(u, v, w);
    }
    Tr.init();

    vi S(q), T(q), X(q), Y(q), St(q), Dr(q), Mij(q), UltNr(q), Total(q);

    for(int i = 0; i < q; ++i) {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        --S[i]; --T[i];
        St[i] = 0;
        Dr[i] = m;
    }
    sort(all(P), [&](auto a, auto b) { return a.second < b.second; });

    int schimbat = 1;
    while(schimbat) {
        schimbat = 0;
        vector<vi> Q(m + 1);///query-uri de dinainte de a aduaga a i - 1 -a muchie
        for(int i = 0; i < q; ++i) {
            if(St[i] != Dr[i]) {
                schimbat = 1;
            }
            Mij[i] = (St[i] + Dr[i] + 1) / 2;
            Q[Mij[i]].push_back(i);
        }
        for(int i = 0; i <= m; ++i) {
            if(i) {
                auto [p, w] = P[i - 1];
                auto [u, v, ceva] = E[p - 1];
                Tr.enable(u, v, w);
            }

            for(auto it : Q[i]) {
                auto [cost, nr] = Tr.query(S[it], T[it]);
                if(cost <= Y[it]) {
                    St[it] = Mij[it];
                    UltNr[it] = nr;
                } else {
                    Dr[it] = Mij[it] - 1;
                }
            }
        }
        if(!schimbat) {
            for(int i = 0; i < q; ++i) {
                Total[i] = Tr.query(S[i], T[i]).second;
            }
        }
        for(int i = 0; i <= m; ++i) {
            if(i) {
                auto [p, w] = P[i - 1];
                auto [u, v, ceva] = E[p - 1];
                Tr.disable(u, v, w);
            }
        }
    }

    for(int i = 0; i < q; ++i) {
        int ramase = X[i] - Total[i] + UltNr[i];
        //printf("Pt query %d  dist=%d  UltNr=%d\n", i, Tr.dist(S[i], T[i]), UltNr[i]);
        cout << max(ramase, -1ll) << "\n";
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In constructor 'tree::tree(ll)':
currencies.cpp:48:37: warning: 'tree::L' will be initialized after [-Wreorder]
   48 |     vector<vector<pair<int, ll> > > L;
      |                                     ^
currencies.cpp:47:8: warning:   'vi tree::par' [-Wreorder]
   47 |     vi par, niv, in, out;
      |        ^~~
currencies.cpp:54:5: warning:   when initialized here [-Wreorder]
   54 |     tree(int N) : n(N), L(N), par(N), niv(N), in(N),
      |     ^~~~

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