oj.uz

Submission #757713

# Submission time Handle Problem Language Result Execution time Memory
757713 2023-06-13T15:35:48 Z ttamx Two Currencies (JOI23_currencies) C++14
100 / 100
 1038 ms 130536 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const bool dbg=false;
const int N=1e5+5;

struct node{
    ll val;
    int freq;
    node *l,*r;
    node():val(0),freq(0),l(nullptr),r(nullptr){}
    node(int val,int freq):val(val),freq(freq),l(nullptr),r(nullptr){}
    node(int val,int freq,node *l,node *r):val(val),freq(freq),l(l),r(r){}
};

typedef node* nodeptr;

void build(int l,int r,nodeptr &t){
    t=new node();
    if(l==r)return;
    int m=(l+r)/2;
    build(l,m,t->l);
    build(m+1,r,t->r);
}

void update(int l,int r,nodeptr &t,nodeptr k,int x,ll val){
    t=new node(*k);
    t->val+=val;
    t->freq++;
    if(l==r)return;
    int m=(l+r)/2;
    if(x<=m)update(l,m,t->l,k->l,x,val);
    else update(m+1,r,t->r,k->r,x,val);
}

int query(int l,int r,vector<pair<nodeptr,nodeptr>> t,ll val){
    if(l==r){
        int res=0;
        for(auto [tl,tr]:t)if(tr->val-tl->val<=val)res+=tr->freq-tl->freq;
        return res;
    }
    int m=(l+r)/2;
    ll sum=0;
    for(auto [tl,tr]:t)sum+=tr->l->val-tl->l->val;
    int freq=0;
    for(auto [tl,tr]:t)freq+=tr->l->freq-tl->l->freq;
    if(sum<=val){
        for(auto &[tl,tr]:t)tl=tl->r,tr=tr->r;
        return freq+query(m+1,r,t,val-sum);
    }
    for(auto &[tl,tr]:t)tl=tl->l,tr=tr->l;
    return query(l,m,t,val);
}

int n,m,q;
int cost[N];
pair<int,int> edge[N];
nodeptr rt[N];
int mp[N];
vector<pair<int,int>> v;
vector<int> vec[N];
vector<int> adj[N];
int sz[N],heavy[N],chain[N],head[N],pos[N],nodeat[N];
int chainid=1,posid;
int pa[N][20],lv[N];
int belong[N];

void dfs(int u,int p){
    lv[u]=lv[p]+1;
    pa[u][0]=p;
    for(int i=1;i<20;i++)pa[u][i]=pa[pa[u][i-1]][i-1];
    sz[u]=1;
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[heavy[u]])heavy[u]=v;
    }
}

int lca(int a,int b){
    if(lv[a]<lv[b])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];
}

void hld(int u,int p){
    pos[u]=++posid;
    nodeat[posid]=u;
    chain[u]=chainid;
    if(heavy[u])hld(heavy[u],u);
    for(auto v:adj[u]){
        if(v==p||v==heavy[u])continue;
        head[++chainid]=v;
        hld(v,u);
    }
}

vector<pair<int,int>> queryup(int st,int ed){
    vector<pair<int,int>> res;
    int u=st;
    while(chain[u]!=chain[ed]){
        res.emplace_back(pos[head[chain[u]]],pos[u]);
        u=pa[head[chain[u]]][0];
    }
    if(ed!=u)res.emplace_back(pos[ed]+1,pos[u]);
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i=1;i<n;i++){
        auto &[u,v]=edge[i];
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1,0);
    head[1]=1;
    hld(1,0);
    for(int i=1;i<=n;i++){
        auto [u,v]=edge[i];
        if(lv[u]<lv[v])swap(u,v);
        belong[i]=u;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> cost[i];
        vec[belong[x]].emplace_back(i);
        v.emplace_back(cost[i],i);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<m;i++)mp[v[i].second]=i+1;
    build(1,m,rt[0]);
    for(int i=1;i<=n;i++){
        rt[i]=rt[i-1];
        for(auto j:vec[nodeat[i]])update(1,m,rt[i],rt[i],mp[j],cost[j]);
    }
    if(dbg){
        for(int i=1;i<=n;i++)cerr << "(" << nodeat[i] << "," << chain[nodeat[i]] << ") ";
        cerr << '\n';
        for(int i=1;i<=chainid;i++)cerr << "(" << i << "," << head[i] << ") ";
    }
    while(q--){
        int u,v,x;
        ll y;
        cin >> u >> v >> x >> y;
        int LCA=lca(u,v);
        vector<pair<nodeptr,nodeptr>> res;
        auto q1=queryup(u,LCA);
        auto q2=queryup(v,LCA);
        for(auto [l,r]:q1)res.emplace_back(rt[l-1],rt[r]);
        for(auto [l,r]:q2)res.emplace_back(rt[l-1],rt[r]);
        int all=0;
        for(auto [tl,tr]:res)all+=tr->freq-tl->freq;
        int cnt=query(1,m,res,y);
        cout << max(-1,x-(all-cnt)) << '\n';
    }
}

Compilation message

currencies.cpp: In function 'int query(int, int, std::vector<std::pair<node*, node*> >, ll)':
currencies.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for(auto [tl,tr]:t)if(tr->val-tl->val<=val)res+=tr->freq-tl->freq;
      |                  ^
currencies.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [tl,tr]:t)sum+=tr->l->val-tl->l->val;
      |              ^
currencies.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [tl,tr]:t)freq+=tr->l->freq-tl->l->freq;
      |              ^
currencies.cpp:51:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto &[tl,tr]:t)tl=tl->r,tr=tr->r;
      |                   ^
currencies.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto &[tl,tr]:t)tl=tl->l,tr=tr->l;
      |               ^
currencies.cpp: In function 'int main()':
currencies.cpp:119:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |         auto &[u,v]=edge[i];
      |               ^
currencies.cpp:128:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |         auto [u,v]=edge[i];
      |              ^
currencies.cpp:133:15: warning: unused variable 'y' [-Wunused-variable]
  133 |         int x,y;
      |               ^
currencies.cpp:158:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |         for(auto [l,r]:q1)res.emplace_back(rt[l-1],rt[r]);
      |                  ^
currencies.cpp:159:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |         for(auto [l,r]:q2)res.emplace_back(rt[l-1],rt[r]);
      |                  ^
currencies.cpp:161:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |         for(auto [tl,tr]:res)all+=tr->freq-tl->freq;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 8 ms 6676 KB Output is correct
6 Correct 10 ms 6716 KB Output is correct
7 Correct 12 ms 6228 KB Output is correct
8 Correct 11 ms 6812 KB Output is correct
9 Correct 10 ms 6868 KB Output is correct
10 Correct 10 ms 6868 KB Output is correct
11 Correct 10 ms 6776 KB Output is correct
12 Correct 10 ms 6880 KB Output is correct
13 Correct 8 ms 6996 KB Output is correct
14 Correct 8 ms 6968 KB Output is correct
15 Correct 9 ms 6868 KB Output is correct
16 Correct 10 ms 6996 KB Output is correct
17 Correct 9 ms 6868 KB Output is correct
18 Correct 12 ms 6868 KB Output is correct
19 Correct 9 ms 6868 KB Output is correct
20 Correct 8 ms 6868 KB Output is correct
21 Correct 9 ms 6868 KB Output is correct
22 Correct 8 ms 6868 KB Output is correct
23 Correct 9 ms 6868 KB Output is correct
24 Correct 9 ms 6848 KB Output is correct
25 Correct 13 ms 6868 KB Output is correct
26 Correct 9 ms 6840 KB Output is correct
27 Correct 8 ms 6860 KB Output is correct
28 Correct 9 ms 6856 KB Output is correct
29 Correct 8 ms 6868 KB Output is correct
30 Correct 9 ms 6848 KB Output is correct
31 Correct 9 ms 6836 KB Output is correct
32 Correct 9 ms 6868 KB Output is correct
33 Correct 8 ms 7020 KB Output is correct
34 Correct 8 ms 6996 KB Output is correct
35 Correct 8 ms 7024 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 10 ms 6832 KB Output is correct
3 Correct 10 ms 6868 KB Output is correct
4 Correct 9 ms 6868 KB Output is correct
5 Correct 655 ms 110892 KB Output is correct
6 Correct 844 ms 98520 KB Output is correct
7 Correct 771 ms 84100 KB Output is correct
8 Correct 626 ms 80840 KB Output is correct
9 Correct 612 ms 86000 KB Output is correct
10 Correct 1038 ms 122288 KB Output is correct
11 Correct 977 ms 122044 KB Output is correct
12 Correct 958 ms 122044 KB Output is correct
13 Correct 1012 ms 122064 KB Output is correct
14 Correct 935 ms 122072 KB Output is correct
15 Correct 802 ms 129828 KB Output is correct
16 Correct 768 ms 130172 KB Output is correct
17 Correct 799 ms 129396 KB Output is correct
18 Correct 1006 ms 122204 KB Output is correct
19 Correct 979 ms 122276 KB Output is correct
20 Correct 934 ms 122388 KB Output is correct
21 Correct 675 ms 121536 KB Output is correct
22 Correct 606 ms 121740 KB Output is correct
23 Correct 583 ms 122040 KB Output is correct
24 Correct 573 ms 122000 KB Output is correct
25 Correct 782 ms 121924 KB Output is correct
26 Correct 770 ms 122268 KB Output is correct
27 Correct 793 ms 121988 KB Output is correct
28 Correct 462 ms 121888 KB Output is correct
29 Correct 464 ms 121900 KB Output is correct
30 Correct 605 ms 122216 KB Output is correct
31 Correct 556 ms 122132 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 8 ms 6996 KB Output is correct
3 Correct 9 ms 7012 KB Output is correct
4 Correct 9 ms 6996 KB Output is correct
5 Correct 409 ms 92032 KB Output is correct
6 Correct 415 ms 78316 KB Output is correct
7 Correct 528 ms 111208 KB Output is correct
8 Correct 685 ms 130332 KB Output is correct
9 Correct 693 ms 130416 KB Output is correct
10 Correct 657 ms 130404 KB Output is correct
11 Correct 588 ms 129900 KB Output is correct
12 Correct 579 ms 129816 KB Output is correct
13 Correct 590 ms 129728 KB Output is correct
14 Correct 392 ms 130272 KB Output is correct
15 Correct 398 ms 130192 KB Output is correct
16 Correct 425 ms 130348 KB Output is correct
17 Correct 435 ms 130536 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 8 ms 6676 KB Output is correct
6 Correct 10 ms 6716 KB Output is correct
7 Correct 12 ms 6228 KB Output is correct
8 Correct 11 ms 6812 KB Output is correct
9 Correct 10 ms 6868 KB Output is correct
10 Correct 10 ms 6868 KB Output is correct
11 Correct 10 ms 6776 KB Output is correct
12 Correct 10 ms 6880 KB Output is correct
13 Correct 8 ms 6996 KB Output is correct
14 Correct 8 ms 6968 KB Output is correct
15 Correct 9 ms 6868 KB Output is correct
16 Correct 10 ms 6996 KB Output is correct
17 Correct 9 ms 6868 KB Output is correct
18 Correct 12 ms 6868 KB Output is correct
19 Correct 9 ms 6868 KB Output is correct
20 Correct 8 ms 6868 KB Output is correct
21 Correct 9 ms 6868 KB Output is correct
22 Correct 8 ms 6868 KB Output is correct
23 Correct 9 ms 6868 KB Output is correct
24 Correct 9 ms 6848 KB Output is correct
25 Correct 13 ms 6868 KB Output is correct
26 Correct 9 ms 6840 KB Output is correct
27 Correct 8 ms 6860 KB Output is correct
28 Correct 9 ms 6856 KB Output is correct
29 Correct 8 ms 6868 KB Output is correct
30 Correct 9 ms 6848 KB Output is correct
31 Correct 9 ms 6836 KB Output is correct
32 Correct 9 ms 6868 KB Output is correct
33 Correct 8 ms 7020 KB Output is correct
34 Correct 8 ms 6996 KB Output is correct
35 Correct 8 ms 7024 KB Output is correct
36 Correct 3 ms 5076 KB Output is correct
37 Correct 10 ms 6832 KB Output is correct
38 Correct 10 ms 6868 KB Output is correct
39 Correct 9 ms 6868 KB Output is correct
40 Correct 655 ms 110892 KB Output is correct
41 Correct 844 ms 98520 KB Output is correct
42 Correct 771 ms 84100 KB Output is correct
43 Correct 626 ms 80840 KB Output is correct
44 Correct 612 ms 86000 KB Output is correct
45 Correct 1038 ms 122288 KB Output is correct
46 Correct 977 ms 122044 KB Output is correct
47 Correct 958 ms 122044 KB Output is correct
48 Correct 1012 ms 122064 KB Output is correct
49 Correct 935 ms 122072 KB Output is correct
50 Correct 802 ms 129828 KB Output is correct
51 Correct 768 ms 130172 KB Output is correct
52 Correct 799 ms 129396 KB Output is correct
53 Correct 1006 ms 122204 KB Output is correct
54 Correct 979 ms 122276 KB Output is correct
55 Correct 934 ms 122388 KB Output is correct
56 Correct 675 ms 121536 KB Output is correct
57 Correct 606 ms 121740 KB Output is correct
58 Correct 583 ms 122040 KB Output is correct
59 Correct 573 ms 122000 KB Output is correct
60 Correct 782 ms 121924 KB Output is correct
61 Correct 770 ms 122268 KB Output is correct
62 Correct 793 ms 121988 KB Output is correct
63 Correct 462 ms 121888 KB Output is correct
64 Correct 464 ms 121900 KB Output is correct
65 Correct 605 ms 122216 KB Output is correct
66 Correct 556 ms 122132 KB Output is correct
67 Correct 3 ms 5076 KB Output is correct
68 Correct 8 ms 6996 KB Output is correct
69 Correct 9 ms 7012 KB Output is correct
70 Correct 9 ms 6996 KB Output is correct
71 Correct 409 ms 92032 KB Output is correct
72 Correct 415 ms 78316 KB Output is correct
73 Correct 528 ms 111208 KB Output is correct
74 Correct 685 ms 130332 KB Output is correct
75 Correct 693 ms 130416 KB Output is correct
76 Correct 657 ms 130404 KB Output is correct
77 Correct 588 ms 129900 KB Output is correct
78 Correct 579 ms 129816 KB Output is correct
79 Correct 590 ms 129728 KB Output is correct
80 Correct 392 ms 130272 KB Output is correct
81 Correct 398 ms 130192 KB Output is correct
82 Correct 425 ms 130348 KB Output is correct
83 Correct 435 ms 130536 KB Output is correct
84 Correct 613 ms 111672 KB Output is correct
85 Correct 604 ms 98092 KB Output is correct
86 Correct 547 ms 71520 KB Output is correct
87 Correct 925 ms 121988 KB Output is correct
88 Correct 953 ms 122208 KB Output is correct
89 Correct 962 ms 121984 KB Output is correct
90 Correct 957 ms 121932 KB Output is correct
91 Correct 937 ms 122088 KB Output is correct
92 Correct 790 ms 127388 KB Output is correct
93 Correct 752 ms 129164 KB Output is correct
94 Correct 909 ms 122396 KB Output is correct
95 Correct 954 ms 122560 KB Output is correct
96 Correct 936 ms 122384 KB Output is correct
97 Correct 934 ms 122388 KB Output is correct
98 Correct 631 ms 121540 KB Output is correct
99 Correct 603 ms 121608 KB Output is correct
100 Correct 605 ms 122048 KB Output is correct
101 Correct 604 ms 121988 KB Output is correct
102 Correct 764 ms 121912 KB Output is correct
103 Correct 794 ms 122036 KB Output is correct
104 Correct 778 ms 121808 KB Output is correct
105 Correct 481 ms 122080 KB Output is correct
106 Correct 513 ms 122072 KB Output is correct
107 Correct 587 ms 121984 KB Output is correct
108 Correct 569 ms 121952 KB Output is correct