Submission #1328513

#TimeUsernameProblemLanguageResultExecution timeMemory
1328513wangzhiyi33Two Currencies (JOI23_currencies)C++20
100 / 100
916 ms66652 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5+2;

int n,m,qu;
vector<ii>adj[maxn];
int p[maxn],c[maxn],tmp[maxn],u[maxn],v[maxn],cnt[maxn];
int in[maxn],out[maxn];
int tim=0;
vector<ii>isi;

int dep[maxn],bin[maxn][20];
void dfs(int cur,int par){
    dep[cur]=dep[par]+1; bin[cur][0]=par;
    in[cur]=++tim;
    for(auto [x,id] : adj[cur]){
        if(x==par)continue;
        cnt[x]+=cnt[cur]+tmp[id];
        dfs(x,cur);
    }
    out[cur]=tim;
}

int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    int slsh=dep[a]-dep[b];

    for(int q=19;q>=0;q--){
        if(slsh>=(1<<q)){
            slsh-=(1<<q);
            a=bin[a][q];
        }
    }
    if(a==b)return a;

    for(int q=19;q>=0;q--){
        if(bin[a][q]!=bin[b][q]){
            a=bin[a][q],b=bin[b][q];
        }
    }
    return bin[a][0];
}

struct fen{
    int tot[maxn];

    void upd(int i,int val){
        for(int q=i;q<maxn;q+=(q & (-q))){
            tot[q]+=val;
        }
    }
    void update(int i,int val){
        upd(in[i],val);
        upd(out[i]+1,-val);
    }

    int query(int i){
        i=in[i];
        int apa=0;
        for(int q=i;q>0;q-=(q & (-q))){
            apa+=tot[q];
        }
        return apa;
    }
};

fen sum,elem;
int ans[maxn];

void solve(int l,int r,vector<array<int,5> >&cand){
    if(l>r || cand.empty())return;
    int mid=(l+r)/2;

    for(int q=l;q<=mid;q++){
        int idx=isi[q].sec;
        if(dep[u[idx]]<dep[v[idx]])swap(u[idx],v[idx]);
        sum.update(u[idx],isi[q].fir);
        elem.update(u[idx],1);
        
    }

    vector<array<int,5> >ya,tdk;
    for(auto [s,t,x,y,idx] : cand){
        int we=sum.query(s)+sum.query(t)-2*sum.query(lca(s,t));
        int bil=elem.query(s)+elem.query(t)-2*elem.query(lca(s,t));

       // cout<<sum.query(s)<<" "<<sum.query(t)<<" "<<idx<<endl;
       // cout<<we<<" "<<bil<<endl;
        if(we<=y){
            y-=we; ans[idx]+=bil;
            ya.pb({s,t,x,y,idx});
        }
        else{
            tdk.pb({s,t,x,y,idx});
        }
    }

    for(int q=l;q<=mid;q++){
        int idx=isi[q].sec;
        if(dep[u[idx]]<dep[v[idx]])swap(u[idx],v[idx]);
        sum.update(u[idx],-isi[q].fir);
        elem.update(u[idx],-1);
    }
    solve(l,mid-1,tdk); solve(mid+1,r,ya);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>qu;
    for(int q=1;q<n;q++){
        cin>>u[q]>>v[q];
        adj[u[q]].pb({v[q],q}); adj[v[q]].pb({u[q],q});
    }

    for(int q=1;q<=m;q++){
        cin>>p[q]>>c[q];
        tmp[p[q]]++;
        isi.pb({c[q],p[q]});
    }
    sort(isi.begin(),isi.end());
    dfs(1,0);
    
    for(int q=1;q<20;q++){
        for(int w=1;w<=n;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
        }
    }
    vector<array<int,5> >cand;
    for(int q=1;q<=qu;q++){
        int s,t,x,y; cin>>s>>t>>x>>y;
        cand.pb({s,t,x,y,q});
    }

    solve(0,m-1,cand);
    for(int q=1;q<=qu;q++){
        auto [s,t,x,y,_]=cand[q-1];
        int bny=cnt[s]+cnt[t]-2*cnt[lca(s,t)];
        if(bny-ans[q]<=x){
            cout<<x-(bny-ans[q])<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...