Submission #758420

#	Time	Username	Problem	Language	Result	Execution time	Memory
758420		Jarif_Rahman	Two Currencies (JOI23_currencies)	C++17	100 / 100	729 ms	51596 KiB

currencies

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

#define int ll

const int K = 19;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    void add(int l, int r, ll x){
        add(l, x);
        if(r+1 < n) add(r+1, -x);
    }
    ll get(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
};

struct query{
    int a, b, c;
    ll g, s;
    int i;
    query(){}
    query(int _a, int _b, int _c, ll _g, ll _s, int _i): a(_a), b(_b), c(_c), g(_g), s(_s), i(_i) {}
};


int n, m, q;
vector<pair<int, ll>> c;
vector<vector<int>> tree;
vector<int> depth, pos, sz;
vector<int> anc[K];
BIT bit1(0), bit2(0);
vector<ll> ans;
vector<pair<int, int>> edges;
vector<query> Q;

int intime = 0;
void dfs(int nd, int ss, int d){
    pos[nd] = intime++;
    depth[nd] = d;
    if(ss != -1) anc[0][nd] = ss;
    for(int x: tree[nd]) if(x != ss) dfs(x, nd, d+1), sz[nd]+=sz[x];
}

int get_anc(int nd, int d){
    for(int i = 0; i < K; i++){
        if(d&1) nd = anc[i][nd];
        d>>=1;
    }
    return nd;
}

int lca(int a, int b){
    if(depth[a] > depth[b]) swap(a, b);
    b = get_anc(b, depth[b]-depth[a]);
    if(a == b) return a;

    for(int i = K-1; i >= 0; i--) if(anc[i][a] != anc[i][b])
        a = anc[i][a], b = anc[i][b];
    return anc[0][a];
}



signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q; cin >> n >> m >> q;

    c.resize(m);
    tree.resize(n);
    depth.resize(n);
    pos.resize(n);
    sz.assign(n, 1);
    fill(anc, anc+K, vector<int>(n, 0));
    bit1 = BIT(n), bit2 = BIT(n);
    ans.resize(q);

    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--, b--;
        tree[a].pb(b);
        tree[b].pb(a);
        edges.pb({a, b});
    }

    dfs(0, -1, 0);
    for(int p = 1; p < K; p++) for(int i = 0; i < n; i++)
        anc[p][i] = anc[p-1][anc[p-1][i]];


    for(auto &[i, x]: c){
        cin >> i >> x, i--;
        auto [a, b] = edges[i];
        if(depth[a] > depth[b]) i = a;
        else i = b;
        bit1.add(pos[i], pos[i]+sz[i]-1, x);
    }
    sort(c.begin(), c.end(), [](pair<int, ll> a, pair<int, ll> b){
        return make_pair(a.sc, a.f) > make_pair(b.sc, b.f);
    });
    c.insert(c.begin(), {0, 0});

    for(int i = 0; i < q; i++){
        int a, b; ll g, s; cin >> a >> b >> g >> s;
        a--, b--;
        int c = lca(a, b);
        a = pos[a], b = pos[b], c = pos[c];
        Q.pb(query(a, b, c, g, s, i));
    }

    function<void(int, int, vector<int>)> pbs = [&](int l, int r, const vector<int>& Qi){
        if(Qi.empty()) return;
        if(l == r){
            bit2.add(pos[c[l].f], pos[c[l].f]+sz[c[l].f]-1, 1);
            for(int i: Qi){
                ans[Q[i].i] = Q[i].g-bit2.get(Q[i].a)-bit2.get(Q[i].b)+bit2.get(Q[i].c)*2;
                ans[Q[i].i] = max(ans[Q[i].i], -1LL);
            }
            bit2.add(pos[c[l].f], pos[c[l].f]+sz[c[l].f]-1, -1);
            return;
        }

        int md = (l+r)/2;
        for(int i = l; i <= md; i++){
            bit1.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, -c[i].sc);
            bit2.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, 1);
        }

        vector<int> A, B;
        for(int i: Qi){
            if(bit1.get(Q[i].a)+bit1.get(Q[i].b)-bit1.get(Q[i].c)*2 > Q[i].s) B.pb(i);
            else A.pb(i);
        }

        pbs(md+1, r, B);
        for(int i = l; i <= md; i++){
            bit1.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, c[i].sc);
            bit2.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, -1);
        }
        pbs(l, md, A);
    };

    vector<int> Qi;
    for(int i = 0; i < q; i++) Qi.pb(i);
    pbs(0, m, Qi);

    for(ll x: ans) cout << x << "\n";

}

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