oj.uz

Submission #855120

# Submission time Handle Problem Language Result Execution time Memory
855120 2023-09-30T07:52:54 Z Warinchai Two Currencies (JOI23_currencies) C++14
100 / 100
 758 ms 147204 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6560 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6532 KB Output is correct
5 Correct 5 ms 8028 KB Output is correct
6 Correct 6 ms 8284 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 6 ms 8284 KB Output is correct
10 Correct 6 ms 8288 KB Output is correct
11 Correct 6 ms 8280 KB Output is correct
12 Correct 6 ms 8280 KB Output is correct
13 Correct 6 ms 8680 KB Output is correct
14 Correct 6 ms 8540 KB Output is correct
15 Correct 6 ms 8284 KB Output is correct
16 Correct 6 ms 8384 KB Output is correct
17 Correct 6 ms 8284 KB Output is correct
18 Correct 6 ms 8284 KB Output is correct
19 Correct 6 ms 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 7 ms 8284 KB Output is correct
24 Correct 6 ms 8284 KB Output is correct
25 Correct 6 ms 8284 KB Output is correct
26 Correct 6 ms 8408 KB Output is correct
27 Correct 6 ms 8296 KB Output is correct
28 Correct 6 ms 8168 KB Output is correct
29 Correct 5 ms 8280 KB Output is correct
30 Correct 5 ms 8280 KB Output is correct
31 Correct 6 ms 8284 KB Output is correct
32 Correct 6 ms 8420 KB Output is correct
33 Correct 5 ms 8540 KB Output is correct
34 Correct 6 ms 8540 KB Output is correct
35 Correct 6 ms 8600 KB Output is correct

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 8284 KB Output is correct
3 Correct 6 ms 8324 KB Output is correct
4 Correct 6 ms 8284 KB Output is correct
5 Correct 379 ms 117072 KB Output is correct
6 Correct 295 ms 103104 KB Output is correct
7 Correct 313 ms 89796 KB Output is correct
8 Correct 278 ms 84680 KB Output is correct
9 Correct 300 ms 92528 KB Output is correct
10 Correct 400 ms 126928 KB Output is correct
11 Correct 430 ms 126912 KB Output is correct
12 Correct 418 ms 126828 KB Output is correct
13 Correct 404 ms 126916 KB Output is correct
14 Correct 415 ms 127424 KB Output is correct
15 Correct 452 ms 141292 KB Output is correct
16 Correct 502 ms 142416 KB Output is correct
17 Correct 461 ms 140736 KB Output is correct
18 Correct 447 ms 127144 KB Output is correct
19 Correct 442 ms 127336 KB Output is correct
20 Correct 435 ms 127144 KB Output is correct
21 Correct 355 ms 127296 KB Output is correct
22 Correct 347 ms 127180 KB Output is correct
23 Correct 370 ms 127420 KB Output is correct
24 Correct 348 ms 127172 KB Output is correct
25 Correct 379 ms 126572 KB Output is correct
26 Correct 367 ms 126776 KB Output is correct
27 Correct 372 ms 127120 KB Output is correct
28 Correct 334 ms 126900 KB Output is correct
29 Correct 338 ms 126936 KB Output is correct
30 Correct 353 ms 126780 KB Output is correct
31 Correct 397 ms 127124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 358 ms 103888 KB Output is correct
6 Correct 330 ms 89628 KB Output is correct
7 Correct 418 ms 118716 KB Output is correct
8 Correct 585 ms 146888 KB Output is correct
9 Correct 583 ms 147204 KB Output is correct
10 Correct 601 ms 147092 KB Output is correct
11 Correct 498 ms 146376 KB Output is correct
12 Correct 491 ms 146756 KB Output is correct
13 Correct 495 ms 147068 KB Output is correct
14 Correct 345 ms 146832 KB Output is correct
15 Correct 358 ms 146992 KB Output is correct
16 Correct 391 ms 147048 KB Output is correct
17 Correct 389 ms 146904 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6560 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6532 KB Output is correct
5 Correct 5 ms 8028 KB Output is correct
6 Correct 6 ms 8284 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 6 ms 8284 KB Output is correct
10 Correct 6 ms 8288 KB Output is correct
11 Correct 6 ms 8280 KB Output is correct
12 Correct 6 ms 8280 KB Output is correct
13 Correct 6 ms 8680 KB Output is correct
14 Correct 6 ms 8540 KB Output is correct
15 Correct 6 ms 8284 KB Output is correct
16 Correct 6 ms 8384 KB Output is correct
17 Correct 6 ms 8284 KB Output is correct
18 Correct 6 ms 8284 KB Output is correct
19 Correct 6 ms 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 7 ms 8284 KB Output is correct
24 Correct 6 ms 8284 KB Output is correct
25 Correct 6 ms 8284 KB Output is correct
26 Correct 6 ms 8408 KB Output is correct
27 Correct 6 ms 8296 KB Output is correct
28 Correct 6 ms 8168 KB Output is correct
29 Correct 5 ms 8280 KB Output is correct
30 Correct 5 ms 8280 KB Output is correct
31 Correct 6 ms 8284 KB Output is correct
32 Correct 6 ms 8420 KB Output is correct
33 Correct 5 ms 8540 KB Output is correct
34 Correct 6 ms 8540 KB Output is correct
35 Correct 6 ms 8600 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 5 ms 8284 KB Output is correct
38 Correct 6 ms 8324 KB Output is correct
39 Correct 6 ms 8284 KB Output is correct
40 Correct 379 ms 117072 KB Output is correct
41 Correct 295 ms 103104 KB Output is correct
42 Correct 313 ms 89796 KB Output is correct
43 Correct 278 ms 84680 KB Output is correct
44 Correct 300 ms 92528 KB Output is correct
45 Correct 400 ms 126928 KB Output is correct
46 Correct 430 ms 126912 KB Output is correct
47 Correct 418 ms 126828 KB Output is correct
48 Correct 404 ms 126916 KB Output is correct
49 Correct 415 ms 127424 KB Output is correct
50 Correct 452 ms 141292 KB Output is correct
51 Correct 502 ms 142416 KB Output is correct
52 Correct 461 ms 140736 KB Output is correct
53 Correct 447 ms 127144 KB Output is correct
54 Correct 442 ms 127336 KB Output is correct
55 Correct 435 ms 127144 KB Output is correct
56 Correct 355 ms 127296 KB Output is correct
57 Correct 347 ms 127180 KB Output is correct
58 Correct 370 ms 127420 KB Output is correct
59 Correct 348 ms 127172 KB Output is correct
60 Correct 379 ms 126572 KB Output is correct
61 Correct 367 ms 126776 KB Output is correct
62 Correct 372 ms 127120 KB Output is correct
63 Correct 334 ms 126900 KB Output is correct
64 Correct 338 ms 126936 KB Output is correct
65 Correct 353 ms 126780 KB Output is correct
66 Correct 397 ms 127124 KB Output is correct
67 Correct 1 ms 6488 KB Output is correct
68 Correct 5 ms 8540 KB Output is correct
69 Correct 5 ms 8540 KB Output is correct
70 Correct 6 ms 8540 KB Output is correct
71 Correct 358 ms 103888 KB Output is correct
72 Correct 330 ms 89628 KB Output is correct
73 Correct 418 ms 118716 KB Output is correct
74 Correct 585 ms 146888 KB Output is correct
75 Correct 583 ms 147204 KB Output is correct
76 Correct 601 ms 147092 KB Output is correct
77 Correct 498 ms 146376 KB Output is correct
78 Correct 491 ms 146756 KB Output is correct
79 Correct 495 ms 147068 KB Output is correct
80 Correct 345 ms 146832 KB Output is correct
81 Correct 358 ms 146992 KB Output is correct
82 Correct 391 ms 147048 KB Output is correct
83 Correct 389 ms 146904 KB Output is correct
84 Correct 404 ms 119032 KB Output is correct
85 Correct 328 ms 103388 KB Output is correct
86 Correct 261 ms 76908 KB Output is correct
87 Correct 526 ms 130720 KB Output is correct
88 Correct 495 ms 130524 KB Output is correct
89 Correct 497 ms 130648 KB Output is correct
90 Correct 505 ms 130580 KB Output is correct
91 Correct 502 ms 130500 KB Output is correct
92 Correct 749 ms 141068 KB Output is correct
93 Correct 758 ms 144472 KB Output is correct
94 Correct 635 ms 131392 KB Output is correct
95 Correct 653 ms 131488 KB Output is correct
96 Correct 638 ms 131524 KB Output is correct
97 Correct 641 ms 131268 KB Output is correct
98 Correct 440 ms 130308 KB Output is correct
99 Correct 432 ms 130820 KB Output is correct
100 Correct 431 ms 130352 KB Output is correct
101 Correct 442 ms 130584 KB Output is correct
102 Correct 489 ms 130396 KB Output is correct
103 Correct 501 ms 130376 KB Output is correct
104 Correct 507 ms 130584 KB Output is correct
105 Correct 404 ms 130552 KB Output is correct
106 Correct 427 ms 130704 KB Output is correct
107 Correct 428 ms 131016 KB Output is correct
108 Correct 469 ms 130444 KB Output is correct