Submission #1303947

#TimeUsernameProblemLanguageResultExecution timeMemory
1303947sunflowerTwo Currencies (JOI23_currencies)C++17
100 / 100
774 ms26796 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)

#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

struct Check {
    int id, cost;

    friend istream& operator >> (istream& in, Check &c) {
        in >> c.id >> c.cost;
        return in;
    }

    bool operator < (const Check &other) const {
        return (cost < other.cost);
    }
};

struct Query {
    int s, t;
    ll gold, silver;

    friend istream& operator >> (istream& in, Query &q) {
        in >> q.s >> q.t >> q.gold >> q.silver;
        return in;
    }
};

struct Edge {
    int u, v;
};

const int LOG = 17;

#define MAX_N 100100
int numNode, M, q;
int timeDFS = 0;

vector<int> adj[MAX_N + 2];
int sta[MAX_N + 2], fin[MAX_N + 2];
int par[LOG + 2][MAX_N + 2];

Edge edges[MAX_N + 2];

Check chk[MAX_N + 2];

Query query[MAX_N + 2];
int Lca[MAX_N + 2], cntQuery[MAX_N + 2], res[MAX_N + 2];
int L[MAX_N + 2], R[MAX_N + 2], G[MAX_N + 2];

struct BIT {
    ll bit[MAX_N + 2];
    int cnt[MAX_N + 2];

    int n;

    void init(int _n) {
        n = _n;
        memset(bit, 0, (_n + 2) * sizeof(ll));
        memset(cnt, 0, (_n + 2) * sizeof(int));
    }

    void update(int x, int v) {
        for (; x <= n; x += x & (-x)) {
            bit[x] += v;
            cnt[x] += (v > 0 ? 1 : -1);
        }
    }

    void updateRange(int l, int r, int v) {
        update(l, v);
        update(r + 1, -v);
    }

    int getCnt(int x) {
        int ans = 0;
        for (; x > 0; x -= x & (-x)) ans += cnt[x];
        return ans;
    }

    ll get(int x) {
        ll ans = 0;
        for (; x > 0; x -= x & (-x)) ans += bit[x];
        return ans;
    }
} fen;

void dfs(int u) {
    sta[u] = ++timeDFS;

    for (int v : adj[u]) {
        if (v == par[0][u]) continue;
        par[0][v] = u;

        FOR(j, 1, LOG) par[j][v] = par[j - 1][par[j - 1][v]];
        dfs(v);
    }

    fin[u] = timeDFS;
}

bool inSubtree(int u, int v) {
    return (sta[u] <= sta[v] && fin[v] <= fin[u]);
}

int lca(int u, int v) {
    if (inSubtree(u, v)) return u;
    if (inSubtree(v, u)) return v;

    FORD(i, LOG, 0) if (par[i][u] != 0 && !inSubtree(par[i][u], v)) u = par[i][u];
    return par[0][u];
}

bool cmp(const int &x, const int &y) {
    return (G[x] < G[y]);
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> numNode >> M >> q;
    FOR(i, 1, numNode - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges[i] = {u, v};
    }

    FOR(i, 1, M) cin >> chk[i];
    FOR(i, 1, q) cin >> query[i];

    sort(chk + 1, chk + 1 + M);

    dfs(1);

    FOR(i, 1, numNode - 1) {
        if (sta[edges[i].u] > sta[edges[i].v]) swap(edges[i].u, edges[i].v);
    }

    FOR(i, 1, q) L[i] = 0, R[i] = M;
    FOR(i, 1, q) Lca[i] = lca(query[i].s, query[i].t);

    fen.init(numNode);

    FOR(i, 1, M) {
        int id = chk[i].id;
        int v = edges[id].v;
        fen.updateRange(sta[v], fin[v], 1);
    }

    FOR(i, 1, q) {
        int u = query[i].s, v = query[i].t;
        cntQuery[i] = fen.getCnt(sta[u]) + fen.getCnt(sta[v]) - 2 * fen.getCnt(sta[Lca[i]]);
        res[i] = -1;
    }

    while (true) {
        vector<int> checks;
        FOR(i, 1, q) if (L[i] <= R[i]) G[i] = (L[i] + R[i]) >> 1, checks.push_back(i);
        if (checks.empty()) break;

        sort(ALL(checks), cmp);

        fen.init(numNode);

        int ptr = 1;
        for (int id : checks) {
            while (ptr <= G[id]) {
                int idEdge = chk[ptr].id;
                int v = edges[idEdge].v;
                fen.updateRange(sta[v], fin[v], chk[ptr].cost);
                ++ptr;
            }

            /// getResults;
            int u = sta[query[id].s], v = sta[query[id].t], r = sta[Lca[id]];

            ll totalVal = fen.get(u) + fen.get(v) - 2 * fen.get(r);
            int totalCnt = fen.getCnt(u) + fen.getCnt(v) - 2 * fen.getCnt(r);

            if (totalVal <= query[id].silver) {
                L[id] = G[id] + 1;
                if (cntQuery[id] - totalCnt <= query[id].gold) {
                    res[id] = query[id].gold - (cntQuery[id] - totalCnt);
                }
            } else R[id] = G[id] - 1;
        }
    }

    FOR(i, 1, q) cout << res[i] << "\n";

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