Submission #855119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855119	2023-09-30T07:51:22 Z	Warinchai	Two Currencies (JOI23_currencies)	C++14	28 / 100	510 ms	148152 KB

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,n,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

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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Runtime error	9 ms	14172 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #2
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	5 ms	8332 KB	Output is correct
3	Correct	6 ms	8112 KB	Output is correct
4	Correct	6 ms	8280 KB	Output is correct
5	Correct	357 ms	119780 KB	Output is correct
6	Correct	323 ms	106688 KB	Output is correct
7	Correct	331 ms	96280 KB	Output is correct
8	Correct	310 ms	90836 KB	Output is correct
9	Correct	303 ms	98436 KB	Output is correct
10	Correct	449 ms	132124 KB	Output is correct
11	Correct	419 ms	131996 KB	Output is correct
12	Correct	426 ms	132200 KB	Output is correct
13	Correct	442 ms	132056 KB	Output is correct
14	Correct	434 ms	132228 KB	Output is correct
15	Correct	510 ms	147092 KB	Output is correct
16	Correct	507 ms	148152 KB	Output is correct
17	Correct	478 ms	146348 KB	Output is correct
18	Correct	454 ms	132772 KB	Output is correct
19	Correct	465 ms	132548 KB	Output is correct
20	Correct	477 ms	132840 KB	Output is correct
21	Correct	344 ms	131784 KB	Output is correct
22	Correct	360 ms	131904 KB	Output is correct
23	Correct	412 ms	131780 KB	Output is correct
24	Correct	373 ms	131984 KB	Output is correct
25	Correct	371 ms	131956 KB	Output is correct
26	Correct	382 ms	132164 KB	Output is correct
27	Correct	402 ms	131872 KB	Output is correct
28	Correct	362 ms	131840 KB	Output is correct
29	Correct	343 ms	131896 KB	Output is correct
30	Correct	373 ms	132176 KB	Output is correct
31	Correct	345 ms	132032 KB	Output is correct

Subtask #3
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6488 KB	Output is correct
2	Correct	5 ms	8540 KB	Output is correct
3	Correct	6 ms	8540 KB	Output is correct
4	Correct	6 ms	8540 KB	Output is correct
5	Correct	389 ms	111200 KB	Output is correct
6	Correct	349 ms	97832 KB	Output is correct
7	Runtime error	68 ms	47304 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #4
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Runtime error	9 ms	14172 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Submission #855119

Compilation message

Subtask #1 0 / 10.0

Subtask #2 28.0 / 28.0

Subtask #3 0 / 30.0

Subtask #4 0 / 32.0

Subtask #1
0 / 10.0

Subtask #2
28.0 / 28.0

Subtask #3
0 / 30.0

Subtask #4
0 / 32.0