Submission #855120

#	Time	Username	Problem	Language	Result	Execution time	Memory
855120		Warinchai	Two Currencies (JOI23_currencies)	C++14	100 / 100	758 ms	147204 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int dp[100005][20];
int lv[100005];
vector<int>v[100005];
vector<long long>cp[100005];
map<pair<int,int>,int>mp;
vector<long long>vl;
struct pstree{
    struct node{
        node *l,*r;
        long long val;
        int cnt;
        node(long long x=0){
            val=x;
            cnt=0;
            l=r=NULL;
        }
    };
    typedef node* pnode;
    pnode root[100005];
    long long getval(pnode x){
        return x?x->val:0;
    }
    long long getcnt(pnode x){
        return x?x->cnt: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 init(){
        build(1,m,root[0]);
    }
    void upd(int st,int en,pnode &x,int pos,long long val,pnode k){
        x=new node(*k);
        if(st==en){
            x->val+=val;
            x->cnt++;
            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->val=getval(x->l)+getval(x->r);
        x->cnt=getcnt(x->l)+getcnt(x->r);
    }
    int fkval(int st,int en,pnode x,pnode y,pnode l,long long val,int cnt){
        if(st==en){
            long long ad=val/vl[st-1];
            ad=min(ad,getcnt(x)+getcnt(y)-2*getcnt(l));
            return cnt+ad;
        }
        //cerr<<st<<" "<<en<<" "<<x->val<<" "<<y->val<<" "<<l->val<<endl;
        long long sum=getval(x->l)+getval(y->l)-2*getval(l->l);
        //cerr<<"sum,val "<<sum<<" "<<val<<endl;
        int m=(st+en)/2;
        if(sum>=val){
            return fkval(st,m,x->l,y->l,l->l,val,cnt);
        }else{
            //cerr<<m+1<<" "<<en<<" "<<x->r<<" "<<y->r<<" "<<val-sum<<" "<<cnt+getcnt(x->l)+getcnt(y->l)-2*getcnt(l->l)<<endl;
            return fkval(m+1,en,x->r,y->r,l->r,val-sum,cnt+getcnt(x->l)+getcnt(y->l)-2*getcnt(l->l));
        }
    }
}pst;
void dfs(int x,int p){
    lv[x]=lv[p]+1;
    dp[x][0]=p;
    pair<int,int>pp={x,p};
    int np=mp[{x,p}];
    pst.root[x]=pst.root[p];
    //cerr<<"x:"<<x<<" "<<np<<endl;
    for(int i=0;i<cp[np].size();i++){
        //cerr<<cp[np][i]<<" ";
        int pos=lower_bound(vl.begin(),vl.end(),cp[np][i])-vl.begin()+1;
        pst.upd(1,m,pst.root[x],pos,cp[np][i],pst.root[x]);
    }
    //cerr<<endl;
    //cout<<x<<" "<<pst.root[x]<<endl;
    for(int i=1;i<20;i++){
        dp[x][i]=dp[dp[x][i-1]][i-1];
    }
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=p)dfs(v[x][i],x);
    }
}
int lca(int a,int b){
    //cerr<<"finding lca "<<a<<" "<<b<<endl;
    if(lv[b]>lv[a])swap(a,b);
    //cerr<<lv[a]<<" "<<lv[b]<<endl;
    for(int i=19;i>=0;i--)if(lv[dp[a][i]]>=lv[b])a=dp[a][i];
    //cerr<<"change lv:"<<" "<<a<<" "<<b<<endl;
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(dp[a][i]!=dp[b][i])a=dp[a][i],b=dp[b][i];
    //cerr<<"bf lca"<<a<<" "<<b<<endl;
    return dp[a][0];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        v[b].push_back(a);
        v[a].push_back(b);
        mp[{a,b}]=i;
        mp[{b,a}]=i;
    }
    for(int i=0;i<m;i++){
        long long p,c;
        cin>>p>>c;
        cp[p].push_back(c);
        vl.push_back(c);
    }
    sort(vl.begin(),vl.end());
    pst.init();
    dfs(1,0);
    for(int i=0;i<q;i++){
        //cerr<<"question "<<i<<endl;
        long long s,t,x,y;
        cin>>s>>t>>x>>y;
        int l=lca(s,t);
        //cerr<<"lca:"<<l<<endl;
        //cerr<<pst.root[s]<<" "<<pst.root[t]<<" "<<pst.root[l]<<endl;
        int sil=pst.fkval(1,m,pst.root[s],pst.root[t],pst.root[l],y,0);
        int all=pst.getcnt(pst.root[s])+pst.getcnt(pst.root[t])-pst.getcnt(pst.root[l])*2;
        int left=all-sil;
        int gl=x-left;
        if(gl>=0){
            cout<<gl<<"\n";
        }else{
            cout<<"-1\n";
        }
        //cerr<<endl;
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<cp[np].size();i++){
      |                 ~^~~~~~~~~~~~~~
currencies.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
currencies.cpp:76:18: warning: variable 'pp' set but not used [-Wunused-but-set-variable]
   76 |     pair<int,int>pp={x,p};
      |                  ^~

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