Submission #1301804

#TimeUsernameProblemLanguageResultExecution timeMemory
1301804Francisco_MartinTwo Currencies (JOI23_currencies)C++20
100 / 100
1195 ms54820 KiB
//JOISC 2023 Two Currencies
//https://oj.uz/problem/view/JOI23_currencies

#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 = 1e5+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])-2*ft.query(tin[x]);
}
void treeupdate(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(n-1), A(m+1), range;
    for(int i=0; i<n-1; i++){
        cin >> a >> b; edge[i]={a,b};
        g[a].push_back(b); g[b].push_back(a);
    }
    dfs(1,0); A[0]={0,1};
    for(int i=1; i<=m; i++){
        cin >> a >> b; a--;
        auto [v,u]=edge[a];
        if(h[v]>h[u]) swap(v,u);
        A[i]={b,u};
    }
    for(int i=1; i<20; i++) for(int j=1; j<=n; j++) anc[i][j]=anc[i-1][anc[i-1][j]];
    sort(A.begin(),A.end()); range.push_back({0,m});
    vector<array<ll,3>> query; vector<vector<array<ll,4>>> bkt(1);
    for(int i=0; i<q; i++){
        cin >> a >> b >> x >> y;
        query.push_back({a,b,x}); bkt[0].push_back({a,b,y,i});
    }
    while((ll)range.size()!=m+1){
        vector<vector<array<ll,4>>> newbkt; 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++) treeupdate(A[j].second,A[j].first);
            for(auto [a,b,y,id]:bkt[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++) treeupdate(A[j].second,A[j].first);
            if(l!=r) newbkt.push_back(L), newrange.push_back({l,mid-1});
            newbkt.push_back(R); newrange.push_back({mid,r});
        }
        swap(bkt,newbkt); swap(range,newrange);
        for(int i=0; i<=m; i++) treeupdate(A[i].second,-A[i].first);
    }
    vector<vector<array<ll,3>>> finbkt(m+1); vll ans(q);
    for(int i=0; i<=m; i++) for(auto [a,b,y,id]:bkt[i]) finbkt[i].push_back({a,b,id});
    for(int i=0; i<=m; i++){
        treeupdate(A[i].second,1);
        for(auto [a,b,id]:finbkt[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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...