Submission #780749

#	Time	Username	Problem	Language	Result	Execution time	Memory
780749		Warinchai	Two Currencies (JOI23_currencies)	C++14	100 / 100	1201 ms	149212 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int pa[100005][20];
int lv[100005];
long long ar[100005];
vector<long long>edcp[100005];
const int N=1e5;
pair<int,long long>cp[100005];
vector<int>v[100005];
pair<int,int>edge[100005];
map<pair<int,int>,int >mp;
struct persist{
    struct node{
        long long sum,freq;
        node *l;
        node *r;
        node(long long v=0,long long f=0){
            sum=v;
            freq=f;
            l=NULL;
            r=NULL;
        }
    };
    typedef node* pnode;
    pnode rt[100005]={};
    long long gsum(pnode x){
        return x?x->sum:0;
    }
    int gfreq(pnode x){
        return x?x->freq:0;
    }
    void build(int st,int en,pnode &x){
        x=new node();
        if(st==en){
            return;
        }
        int m=(st+en)/2;
        build(st,m,x->l);
        build(m+1,en,x->r);
    }
    void build(){
        build(1,N,rt[0]);
    }
    void upd(int st,int en,pnode &x,long long pos,long long val,pnode k){
        if(k==NULL){
            cout<<"NULL"<<endl;
        }
        x=new node(*k);
        if(st==en){
            x->sum+=val;
            x->freq++;
            return;
        }
        int m=(st+en)/2;
        if(pos<=m){
            upd(st,m,x->l,pos,val,k->l);
        }else{
            upd(m+1,en,x->r,pos,val,k->r);
        }
        x->sum=gsum(x->l)+gsum(x->r);
        x->freq=gfreq(x->l)+gfreq(x->r);
    }
    void upd(int st,int en,long long pos,long long val,int check){
        if(check==0){
            rt[en]=new node(*rt[st]);
            return;
        }
        if(rt[en]==NULL){
            upd(1,N,rt[en],pos,val,rt[st]);
        }else{
            upd(1,N,rt[en],pos,val,rt[en]);
        }
    }
    long long fans(int st,int en,pnode p,pnode x,pnode y,long long k){
        //cout<<st<<" "<<en<<" "<<k<<":"<<endl;
        if(st==en){
            long long f=x->freq+y->freq-2*p->freq;
            //cout<<st<<" "<<ar[st]<<endl;
            if(f==0){
                return 0;
            }
            long long id=ar[st];
            long long ans=min(k/id,f);
            return ans;
        }
        //cout<<"sum: "<<gsum(x->l)<<" "<<gsum(p->l)<<" "<<gsum(y->l)<<" "<<gsum(p->l)<<" "<<endl;
        long long sum=gsum(x->l)-gsum(p->l)+gsum(y->l)-gsum(p->l);
        long long freq=gfreq(x->l)-gfreq(p->l)+gfreq(y->l)-gfreq(p->l);
        //cout<<"sum,freq:"<<sum<<" "<<freq<<endl;
        int m=(st+en)/2;
        if(k<=sum){
            //cout<<"go left"<<endl;
            return fans(st,m,p->l,x->l,y->l,k);
        }else{
            //cout<<"go right"<<endl;
            return fans(m+1,en,p->r,x->r,y->r,k-sum)+freq;
        }
    }
    long long fans(int p,int x,int y,long long k){
        return fans(1,N,rt[p],rt[x],rt[y],k);
    }
}pst;
void dfs(int i,int p){
    //cout<<i<<" "<<p<<endl;
    pa[i][0]=p;
    lv[i]=lv[p]+1;
    for(int j=1;j<20;j++){
        pa[i][j]=pa[pa[i][j-1]][j-1];
    }
    int ednum=mp[{i,p}];
    for(int j=0;j<edcp[ednum].size();j++){
        long long b=edcp[ednum][j];
        int num=lower_bound(ar,ar+m+1,b)-ar;
        //cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<endl;
        pst.upd(p,i,num,b,1);
    }
    if(edcp[ednum].size()==0){
        //cout<<"upd:NO UPD"<<endl;
        pst.upd(p,i,0,0,0);
    }
    /*int id=mp[{i,p}];
    int b=cp[id].second;
    int num=lower_bound(ar,ar+m+1,b)-ar;
    cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<id<<endl;
    pst.upd(p,i,num,b);*/
    for(int j=0;j<v[i].size();j++){
        if(v[i][j]!=p){
            dfs(v[i][j],i);
        }
    }
}
int lca(int a,int b){
    if(lv[b]>lv[a]){
        swap(a,b);
    }
    for(int i=19;i>=0;i--){
        if(lv[pa[a][i]]>=lv[b]){
            a=pa[a][i];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=19;i>=0;i--){
        if(pa[a][i]!=pa[b][i]){
            a=pa[a][i];
            b=pa[b][i];
        }
    }
    return pa[a][0];
}
int main(){
    cin>>n>>m>>q;
    pst.build();
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        edge[i].first=a;
        edge[i].second=b;
        mp[{a,b}]=i;
        mp[{b,a}]=i;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cp[i]={a,b};
        int ednum=a;
        edcp[a].push_back(b);
        ar[i]=b;
    }
    /*for(int i=0;i<=n;i++){
        cout<<ar[i]<<" ";
    }*/
    cout<<endl;
    sort(ar+1,ar+m+1);
    pst.upd(0,1,1,0,0);
    dfs(1,0);
    //cout<<"work"<<endl;
    for(int i=1;i<=q;i++){
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        int x=lca(a,b);
        int sz=pst.fans(x,a,b,LLONG_MAX);
        //cout<<"SIZE IS "<<sz<<endl;
        //cout<<"info"<<endl;
        //cout<<x<<" "<<a<<" "<<b<<endl;
        int use=pst.fans(x,a,b,d);
        sz-=use;
        c-=sz;
        //cout<<"ANS::";
        if(c<0){
            cout<<"-1\n";
        }else{
            cout<<c<<"\n";
        }
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int j=0;j<edcp[ednum].size();j++){
      |                 ~^~~~~~~~~~~~~~~~~~~
currencies.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:170:13: warning: unused variable 'ednum' [-Wunused-variable]
  170 |         int ednum=a;
      |             ^~~~~

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