Submission #1301669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301669		Francisco_Martin	Two Currencies (JOI23_currencies)	C++20	100 / 100	1798 ms	96464 KiB

currencies

//JOISC 2023 Two Currencies
//https://oj.uz/problem/view/JOI23_passport

#include <bits/stdc++.h>
using namespace std;
#define fastIO cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
using ll = long long;
using vll = vector<ll>;
const ll MAXN = 2e5+5;

struct Fenwick{
    vll bit; ll size;
    Fenwick(ll n){bit.assign(n+1,0); size=n;}
    void update(ll pos,ll delta){
        for(; pos<=size; pos+=pos&-pos) bit[pos]+=delta;
    }
    ll query(ll pos){
        ll res=0;
        for(; pos>0; pos-=pos&-pos) res+=bit[pos];
        return res;
    }
};

vll g[MAXN], tin(MAXN), tout(MAXN), h(MAXN,0), val(MAXN,0); 
vector<vll> anc(20,vll(MAXN,0)); Fenwick ft(MAXN); ll t=1;

void dfs(ll v,ll p){
    tin[v]=t++; anc[0][v]=p; h[v]=h[p]+1;
    for(auto u:g[v]) if(u!=p) dfs(u,v);
    tout[v]=t-1;
}

ll kanc(ll v,ll k){
    for(int i=0; i<20; i++) if((k>>i)&1) v=anc[i][v];
    return v;
}
ll lca(ll v,ll u){
    if(h[v]>h[u]) swap(v,u);
    u=kanc(u,h[u]-h[v]);
    if(v==u) return v;
    for(int i=19; i>=0; i--) if(anc[i][v]!=anc[i][u]){
        v=anc[i][v]; u=anc[i][u];
    }
    return anc[0][v];
}

ll dist(ll v,ll u){
    ll x=lca(v,u);
    return ft.query(tin[v])+ft.query(tin[u])-ft.query(tin[x])-ft.query(tin[anc[0][x]]);
}
void add(ll v,ll delta){
    ft.update(tin[v],delta); ft.update(tout[v]+1,-delta);
}

int main(){
    fastIO;
    ll n, m, q, a, b, x, y;
    cin >> n >> m >> q;
    vector<pair<ll,ll>> edge, ord; vector<array<ll,3>> query;
    for(int i=0; i<n-1; i++){
        cin >> a >> b; edge.push_back({a,b});
    }
    for(int i=1; i<=m; i++){
        cin >> a >> b; a--;
        auto [v,u]=edge[a]; val[n+i]=b;
        edge[a]={v,n+i}; edge.push_back({n+i,u});
    }
    for(auto [a,b]:edge) g[a].push_back(b), g[b].push_back(a);
    dfs(1,0);
    for(int i=1; i<20; i++) for(int j=1; j<=n+m; j++){
        anc[i][j]=anc[i-1][anc[i-1][j]];
    }
    for(int i=1; i<=n+m; i++) ord.push_back({val[i],i});
    sort(ord.begin(),ord.end()); 
    vector<pair<ll,ll>> range; range.push_back({0,n+m-1});
    vector<vector<array<ll,4>>> node(1);
    for(int i=0; i<q; i++){
        cin >> a >> b >> x >> y;
        query.push_back({a,b,x}); node[0].push_back({a,b,y,i});
    }
    auto solve=[&](){
        vector<vector<array<ll,4>>> newnode; vector<pair<ll,ll>> newrange;
        for(int i=0; i<(ll)range.size(); i++){
            auto [l,r]=range[i]; ll mid=(l+r+1)/2; 
            vector<array<ll,4>> L, R;
            for(int j=l; j<=mid; j++) add(ord[j].second,val[ord[j].second]);
            for(auto [a,b,y,id]:node[i]){
                if(dist(a,b)>y) L.push_back({a,b,y,id});
                else R.push_back({a,b,y,id});
            }
            for(int j=mid+1; j<=r; j++) add(ord[j].second,val[ord[j].second]);
            if(l!=r) newnode.push_back(L), newrange.push_back({l,mid-1});
            newnode.push_back(R); newrange.push_back({mid,r});
        }
        swap(node,newnode); swap(range,newrange);
        for(int i=1; i<=n+m; i++) add(i,-val[i]);
    };
    while((ll)range.size()!=n+m) solve();
    vector<vector<array<ll,3>>> newquery(n+m); vll ans(q);
    for(int i=0; i<n+m; i++) for(auto [a,b,y,id]:node[i]){
        newquery[i].push_back({a,b,id});
    }
    for(int i=0; i<n+m; i++){
        add(ord[i].second,1);
        for(auto [a,b,id]:newquery[i]) ans[id]=dist(a,b);
    }
    for(int i=0; i<q; i++){
        auto [a,b,x]=query[i];
        cout << max(x-dist(a,b)+ans[i],(ll)-1) << "\n";
    }
    return 0;
}

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