Submission #1247303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247303		wcarrotw	Two Currencies (JOI23_currencies)	C++17	28 / 100	124 ms	32652 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int LOG = 17;

// Cấu trúc cạnh
struct Edge { int to, id; };

// Persistent SegTree node
struct PST {
    PST *l, *r;
    int cnt;
    long long sum;
    PST(int _cnt=0, long long _sum=0, PST* _l=nullptr, PST* _r=nullptr)
      : l(_l), r(_r), cnt(_cnt), sum(_sum) {}
};

PST *nullNode = new PST();

// Cập nhật PST (thêm deltaCnt checkpoint có giá trị = val tại vị trí pos)
PST* update(PST* prev, int L, int R, int pos, int deltaCnt, int val) {
    if (pos < L || pos > R) return prev;
    if (L == R) {
        return new PST(prev->cnt + deltaCnt,
                       prev->sum + 1LL * deltaCnt * val,
                       nullNode, nullNode);
    }
    int M = (L + R) >> 1;
    PST *left = prev->l, *right = prev->r;
    if (pos <= M)
        left = update(prev->l,   L, M, pos, deltaCnt, val);
    else
        right = update(prev->r, M+1, R, pos, deltaCnt, val);
    return new PST(left->cnt + right->cnt,
                   left->sum + right->sum,
                   left, right);
}

// Truy vấn tổng sum trên đoạn [lq..rq]
long long querySum(PST* U, PST* V, PST* A, PST* B,
                   int L, int R, int lq, int rq) {
    if (rq < L || R < lq) return 0;
    if (lq <= L && R <= rq) {
        return U->sum + V->sum - A->sum - B->sum;
    }
    int M = (L + R) >> 1;
    return querySum(U->l, V->l, A->l, B->l, L, M, lq, rq)
         + querySum(U->r, V->r, A->r, B->r, M+1, R, lq, rq);
}

// Truy vấn cnt trên đoạn [lq..rq]
int queryCnt(PST* U, PST* V, PST* A, PST* B,
             int L, int R, int lq, int rq) {
    if (rq < L || R < lq) return 0;
    if (lq <= L && R <= rq) {
        return U->cnt + V->cnt - A->cnt - B->cnt;
    }
    int M = (L + R) >> 1;
    return queryCnt(U->l, V->l, A->l, B->l, L, M, lq, rq)
         + queryCnt(U->r, V->r, A->r, B->r, M+1, R, lq, rq);
}

// Tìm số checkpoint lớn nhất (bắt đầu từ giá trị cao) cần dùng để đạt tổng ≥ need
int getMinUsed(PST* U, PST* V, PST* A, PST* B,
               int L, int R, long long need,
               const vector<int>& allVals) {
    if (need <= 0) return 0;
    if (L == R) {
        long long val = allVals[L];
        // đảm bảo val > 0 (theo đề bài, checkpoint luôn > 0)
        return int((need + val - 1) / val);
    }
    int M = (L + R) >> 1;
    // tổng của nửa phải (giá trị lớn hơn)
    long long sumR = querySum(U->r, V->r, A->r, B->r, M+1, R, M+1, R);
    int cntR   = queryCnt(U->r, V->r, A->r, B->r, M+1, R, M+1, R);
    if (sumR >= need) {
        return getMinUsed(U->r, V->r, A->r, B->r, M+1, R, need, allVals);
    } else {
        return cntR + getMinUsed(U->l, V->l, A->l, B->l, L, M, need - sumR, allVals);
    }
}

int N, M, Q;
vector<Edge> g[MAXN];
vector<int> edgeChk[MAXN];
int depthArr[MAXN], parentArr[MAXN][LOG];
PST* root[MAXN];
vector<int> allVals;

// Xây dựng root[v] và parentArr[v][0] qua DFS
void dfs(int u, int p) {
    for (auto &e : g[u]) {
        int v = e.to, eid = e.id;
        if (v == p) continue;
        depthArr[v] = depthArr[u] + 1;
        parentArr[v][0] = u;
        // kế thừa PST của u
        PST* curr = root[u];
        // thêm các checkpoint của cạnh (u->v)
        for (int c : edgeChk[eid]) {
            int pos = int(lower_bound(allVals.begin(), allVals.end(), c) - allVals.begin());
            curr = update(curr, 0, (int)allVals.size() - 1, pos, 1, c);
        }
        root[v] = curr;
        dfs(v, u);
    }
}

// Tìm LCA
int lca(int u, int v) {
    if (depthArr[u] < depthArr[v]) swap(u, v);
    int diff = depthArr[u] - depthArr[v];
    for (int k = 0; k < LOG; ++k)
        if (diff >> k & 1) u = parentArr[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k) {
        if (parentArr[u][k] != parentArr[v][k]) {
            u = parentArr[u][k];
            v = parentArr[v][k];
        }
    }
    return parentArr[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> Q;
    // đọc cây
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    // đọc checkpoint
    for (int i = 0; i < M; ++i) {
        int p, c;
        cin >> p >> c;
        edgeChk[p-1].push_back(c);
        allVals.push_back(c);
    }
    // nén giá trị
    sort(allVals.begin(), allVals.end());
    allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());

    // khởi tạo nullNode
    nullNode->l = nullNode->r = nullNode;
    nullNode->cnt = nullNode->sum = 0;
    // gốc PST tại node 1
    root[1] = nullNode;
    depthArr[1] = 0;
    parentArr[1][0] = 1;

    // DFS để build PST và parentArr[][0]
    dfs(1, 0);
    // build parentArr cho binary lifting
    for (int k = 1; k < LOG; ++k) {
        for (int v = 1; v <= N; ++v) {
            parentArr[v][k] = parentArr[ parentArr[v][k-1] ][k-1];
        }
    }

    // xử lý truy vấn
    while (Q--) {
        int s, t;
        long long X, Y;
        cin >> s >> t >> X >> Y;
        int c = lca(s, t);

        // tính tổng silver trên đường s->t
        long long sumS = root[s]->sum + root[t]->sum
                       - 2LL * root[c]->sum;
        if (sumS <= Y) {
            cout << X << "\n";
            continue;
        }
        long long need = sumS - Y;
        // tìm số checkpoint cần dùng
        // B = root[parentArr[c][0]] (nếu c==1 thì parentArr[1][0]=1 => root[1]=nullNode)
        PST* nodeA = root[c];
        PST* nodeB = root[ parentArr[c][0] ];
        int used = getMinUsed(root[s], root[t], nodeA, nodeB,
                              0, (int)allVals.size() - 1,
                              need, allVals);
        if (used <= X) cout << (X - used) << "\n";
        else          cout << "-1\n";
    }
    return 0;
}

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