Submission #930169

#	Time	Username	Problem	Language	Result	Execution time	Memory
930169		alexz1205	Two Currencies (JOI23_currencies)	C++14	0 / 100	10 ms	11100 KiB

currencies

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

const int N = 1e5, M = 1e5, Q = 1e5;
typedef long long int lint;

int n, m, q;

struct edgePair{
    int a, b;
    vector<lint> t;
};

struct edge{
    int v;
    vector<lint> t;
};

struct SegTree{
    int l, r;
    lint tot, size;
    SegTree* lChild;
    SegTree* rChild;

    SegTree(int l, int r){
        this->l = l;
        this->r = r;
        tot = 0;
        size = 0;
        if (l+1 < r){
            lChild = new SegTree(l, (r-l+1)/2+l);
            rChild = new SegTree((r-l+1)/2+l, r);
        }else {
            lChild = NULL;
            rChild = NULL;
        }
    }

    SegTree(int l, int r, SegTree* lC, SegTree* rC){
        this->l = l;
        this->r = r;
        lChild = lC;
        rChild = rC;
        if (lChild != NULL){
            tot = lChild->tot+rChild->tot;
            size = lChild->size + rChild->size;
        }else {
            tot = 0;
            size = 0;
        }
    }

    SegTree* add(int p, int v){
        SegTree* n = new SegTree(l, r, lChild, rChild);
        n->tot += v;
        n->size ++;
        if (lChild == NULL){
            return n;
        }else {
            int m = (r-l+1)/2+l;
            if (p < m){
                n->lChild = lChild->add(p, v);
            }else {
                n->rChild = rChild->add(p, v);
            }
        }
        return n;
    }
};

edgePair edges[N];
map<lint, int> comp;

SegTree* trees[N];

vector<edge> con[N];

int binJump[N][20];
int dep[N];

int checks[M];
int pos[M];

void dfs(int i, int p){
    binJump[i][0] = p;
    for (edge e: con[i]){
        if (e.v == p){
            continue;
        }
        SegTree* nex = trees[i];
        for (int x: e.t){
            nex = nex->add(pos[x], checks[x]);
        }
        dep[e.v] = dep[i]+1;
        trees[e.v] = nex;
        dfs(e.v, i);
    }
}

void calcBinJump(){
    for (int x = 1; x < 20; x ++){
        for (int i = 0; i < n; i ++){
            binJump[x][i] = binJump[binJump[x][i-1]][i-1];
        }
    }
}

int lca(int a, int b){
    int dif = dep[a]-dep[b];
    while (dif > 0){
        int i = 31-__builtin_ctz(dif);
        a = binJump[a][i];
        dif = dep[a]-dep[b];
    }
    swap(a, b);
    dif = dep[a]-dep[b];
    while (dif > 0){
        int i = 31-__builtin_ctz(dif);
        a = binJump[a][i];
        dif = dep[a]-dep[b];
    }
    while (a != b){
        int i = 0;
        for (; i < 20; i ++){
            if (binJump[a][i] == binJump[b][i]){
                break;
            }
        }
        i = max(0, i-1);
        a = binJump[a][i];
        b = binJump[b][i];
    }
    return a;
}

lint minGold(int s, int t, int a , lint Y){
    SegTree *sP = trees[s], *tP = trees[t], *aP = trees[a];
    lint notReq = 0, req = sP->size + tP->size - 2*aP->size;
    // cout << "HI" << endl;
    while (true){
        if (sP->lChild == NULL){
            lint v = sP->tot + tP->tot - 2*aP->tot;
            if (v > Y){
            }else {
                notReq += sP->size + tP->size - 2*aP->size;
                Y -= v;
            }
            break;
        }
        // printf("%d, %d, %d, %d, %d, %d \n", sP->l, sP->r, tP->l, tP->r, aP->l, aP->r);
        lint v = sP->lChild->tot + tP->lChild->tot - 2*aP->lChild->tot;
        if (v > Y){
            sP = sP->lChild;
            tP = tP->lChild;
            aP = aP->lChild;
        }else {
            notReq += sP->lChild->size + tP->lChild->size - 2*aP->lChild->size;
            sP = sP->rChild;
            tP = tP->rChild;
            aP = aP->rChild;
            Y -= v;
        }
    }

    return req-notReq;
}

int main(){
    cin >> n >> m >> q;
    for (int x = 0; x < n-1; x ++){
        int a, b;
        cin >> a >> b;
        a --, b --;
        edges[x] = {a, b, {}};
    }
    // cout << "HI" << endl;
    vector<pair<int, int>> vals;
    for (int x = 0; x < m; x ++){
        lint p, v;
        cin >> p >> v;
        p --;
        checks[x] = v;
        vals.push_back({v, x});
        edges[p].t.push_back(x);
    }
    sort(vals.begin(), vals.end());
    // cout << "HI" << endl;
    for (int x = 0; x < m; x ++){
        pos[vals[x].second] = x;
    }
    for (int x = 0; x < n-1; x ++){
        int a = edges[x].a, b = edges[x].b;
        con[a].push_back({b, edges[x].t});
        con[b].push_back({a, edges[x].t});
    }
    // cout << "HI" << endl;
    trees[0] = new SegTree(0, m);
    dfs(0, 0);
    calcBinJump();
    // cout << "HI" << endl;
    for (int x = 0; x < q; x ++){
        lint s, d, X, Y;
        cin >> s >> d >> X >> Y;
        s --, d --;
        lint a = lca(s, d);
        // cout << x << endl;
        cout << max(-1LL, X-minGold(s, d, a, Y)) << endl;
    }
}

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