oj.uz

Submission #964957

# Submission time Handle Problem Language Result Execution time Memory
964957 2024-04-17T19:24:17 Z YassirSalama Two Currencies (JOI23_currencies) C++17
100 / 100
 3613 ms 115092 KB 
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
#define int ll
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=1e5+100;
const int lgn=20;
vector<int> v[mxn];
int depth[mxn];
int up[mxn][lgn+1];
int top[mxn];
int pos[mxn];
int BIT1[mxn];
int BIT2[mxn];
int sum[mxn];
int ans[mxn];
int nm[mxn];
int sz[mxn];
map<pii,int> mp,mp1,mp2;
map<int,pii> mp3;
vector<tuple<int,int,int>> f;
vector<vector<int>> queries;
int n,m,q;
void add(int i,int x){
    i++;
    while(i<mxn){
        BIT1[i]+=x;
        BIT2[i]+=(x>0?1:-1);
        i+=i&-i;
    }
}
pii qq(int i){
    i++;
    int ans1=0,ans2=0;
    while(i){
        ans1+=BIT1[i];
        ans2+=BIT2[i];
        i-=i&-i;
    }
    return {ans1,ans2};
}
pii s(int l,int r){
    if(l>r) return {0,0};
    pii a=qq(l-1),b=qq(r);
    return {b.F-a.F,b.S-a.S};
}
void dfs(int node,int par){
    depth[node]=depth[par]+1;
    up[node][0]=par;
    for(int i=1;i<=lgn;i++){
        up[node][i]=up[up[node][i-1]][i-1];
    }
    sz[node]=1;
    for(auto x:v[node]){
        if(x==par) continue;
        dfs(x,node);
        sz[node]+=sz[x];
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    int d=depth[a]-depth[b];
    for(int i=lgn;i>=0;i--){
        if(d&(1LL<<i)) a=up[a][i];
    }
    if(a==b) return a;
    for(int i=lgn;i>=0;i--){
        if(up[a][i]==up[b][i]) continue;
        a=up[a][i];
        b=up[b][i];
    }
    return up[a][0];
}
int c=1;
void HLD(int node,int par,int cID){
   top[node]=cID;
   pos[node]=c;
   c++;
   int bst=-1;
   int b=0;
   for(auto x:v[node]){
       if(x==par) continue;
       if(bst<sz[x]){
           bst=sz[x];
           b=x;
       }
   }
   if(bst!=-1){
       HLD(b,node,cID);
   }
   for(auto x:v[node]){
       if(x==par) continue;
       if(x==b) continue;
       HLD(x,node,x);
   }
}
pii query(int u,int v){
    pair<int,int> ans(0,0);
    int vv=v;
    while(top[u]!=top[v]){
        int l=top[v];
        l=pos[l];
        l++;
        int r=pos[v];
        pii a=s(l,r);
        ans.F+=a.F;
        ans.S+=a.S;
        v=top[v];
        if(mp1.count({up[v][0],v})){
            ans.F+=mp1[{up[v][0],v}];
            ans.S+=mp2[{up[v][0],v}];
        }
        v=up[v][0];
    }
    int l=u;
    l=pos[u];
    l++;
    int r=pos[v];
    pii a=s(l,r);
    // if(u==1&&v==7){
    //     dbg(l,r,u,top[v],a.F,a.S)
    // }
    ans.F+=a.F;
    ans.S+=a.S;
    return ans;
}
void bs(int l,int r,vector<vector<int>> &queries){
    mp1.clear();
    mp2.clear();
    // dbg(l,r)
    if(queries.empty()) return;
    vector<vector<int>> ok,nok;
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++){
        auto [c,a,b]=f[i];
        if(up[a][0]==b) swap(a,b);
        add(pos[b],c);
        mp1[{a,b}]+=c;
        mp2[{a,b}]++;
    }
    for(auto x:queries){
        pii ans(0,0);
        int L=LCA(x[0],x[1]);
        pii a=query(L,x[0]),b=query(L,x[1]);
        ans.F=a.F+b.F;
        ans.S=a.S+b.S;
        // if(x[4]==1){
        //     dbg(l,mid,r,a.F,a.S,ans.F,ans.S,sum[x[4]],nm[x[4]])
        // }
        if(sum[x[4]]>=ans.F){
            sum[x[4]]-=ans.F;
            nm[x[4]]-=ans.S;
            // if(x[4]==1){
            //     dbg(2,l,mid,r,a.F,a.S,ans.F,ans.S,sum[x[4]],nm[x[4]])
            // }

            ok.pb(x);
        }else nok.pb(x);
    }
    for(int i=l;i<=mid;i++){
        auto [c,a,b]=f[i];
        if(up[a][0]==b) swap(a,b);
        add(pos[b],-c);
    }
    if(l>=r) return;

    bs(l,mid,nok);
    bs(mid+1,r,ok);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>q;
for(int i=0;i+1<n;i++){
    int a,b;
    cin>>a>>b;
    v[a].pb(b);
    v[b].pb(a);
    mp3[i]={a,b};
    mp[{a,b}]=mp[{b,a}]=i;
}
for(int i=0;i<m;i++){
    int p,c;
    cin>>p>>c;
    p--;
    auto [a,b]=mp3[p];
    f.pb({c,a,b});
}
sort(all(f));
for(int i=0;i<q;i++){
    int s,t,x,y;
    cin>>s>>t>>x>>y;
    queries.pb({s,t,x,y,i});
    sum[i]=y;
}
dfs(1,1);
HLD(1,1,1);
for(int i=0;i<m;i++){
    auto [c,a,b]=f[i];
    if(up[a][0]==b) swap(a,b);
    add(pos[b],c);
    mp1[{a,b}]+=c;
    mp2[{a,b}]++;
}
for(auto x:queries){
    int l=LCA(x[0],x[1]);
    pii a = query(l,x[0]),b=query(l,x[1]);
    nm[x[4]]=a.S+b.S;
    // dbg(x[4],nm[x[4]])
}
for(int i=0;i<m;i++){
    auto [c,a,b]=f[i];
    if(up[a][0]==b) swap(a,b);
    add(pos[b],-c);
    mp1.erase({a,b});
    mp2.erase({a,b});
}
bs(0,m-1,queries);
for(auto x:queries){
    int a=x[0];
    int b=x[1];
    dbg(a,b,nm[x[4]],sum[x[4]],x[4])
    if(nm[x[4]]>x[2]) ans[x[4]]=-1;
    else ans[x[4]]=x[2]-nm[x[4]];
}
for(int i=0;i<q;i++){
    cout<<ans[i]<<endl;
}

}

Compilation message

currencies.cpp: In function 'pii query(ll, ll)':
currencies.cpp:116:9: warning: unused variable 'vv' [-Wunused-variable]
  116 |     int vv=v;
      |         ^~
currencies.cpp: In function 'int main()':
currencies.cpp:17:18: warning: statement has no effect [-Wunused-value]
   17 | #define dbg(...) 1337;
      |                  ^~~~
currencies.cpp:238:5: note: in expansion of macro 'dbg'
  238 |     dbg(a,b,nm[x[4]],sum[x[4]],x[4])
      |     ^~~
currencies.cpp:236:9: warning: unused variable 'a' [-Wunused-variable]
  236 |     int a=x[0];
      |         ^
currencies.cpp:237:9: warning: unused variable 'b' [-Wunused-variable]
  237 |     int b=x[1];
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9564 KB Output is correct
2 Correct 3 ms 9636 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 15 ms 12776 KB Output is correct
6 Correct 23 ms 13136 KB Output is correct
7 Correct 18 ms 12892 KB Output is correct
8 Correct 23 ms 12972 KB Output is correct
9 Correct 28 ms 12916 KB Output is correct
10 Correct 23 ms 12944 KB Output is correct
11 Correct 22 ms 12940 KB Output is correct
12 Correct 25 ms 12892 KB Output is correct
13 Correct 14 ms 12888 KB Output is correct
14 Correct 15 ms 12948 KB Output is correct
15 Correct 17 ms 12948 KB Output is correct
16 Correct 17 ms 12908 KB Output is correct
17 Correct 18 ms 12892 KB Output is correct
18 Correct 17 ms 12724 KB Output is correct
19 Correct 16 ms 13144 KB Output is correct
20 Correct 16 ms 13144 KB Output is correct
21 Correct 17 ms 13228 KB Output is correct
22 Correct 16 ms 13148 KB Output is correct
23 Correct 17 ms 13036 KB Output is correct
24 Correct 17 ms 13072 KB Output is correct
25 Correct 16 ms 13144 KB Output is correct
26 Correct 18 ms 12892 KB Output is correct
27 Correct 14 ms 13144 KB Output is correct
28 Correct 15 ms 13104 KB Output is correct
29 Correct 14 ms 13916 KB Output is correct
30 Correct 23 ms 12936 KB Output is correct
31 Correct 20 ms 12888 KB Output is correct
32 Correct 20 ms 12892 KB Output is correct
33 Correct 12 ms 13144 KB Output is correct
34 Correct 14 ms 12888 KB Output is correct
35 Correct 13 ms 12892 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 19 ms 12940 KB Output is correct
3 Correct 20 ms 12916 KB Output is correct
4 Correct 23 ms 12880 KB Output is correct
5 Correct 2164 ms 93392 KB Output is correct
6 Correct 2478 ms 101244 KB Output is correct
7 Correct 2531 ms 105908 KB Output is correct
8 Correct 1909 ms 88336 KB Output is correct
9 Correct 1851 ms 87108 KB Output is correct
10 Correct 2878 ms 83180 KB Output is correct
11 Correct 3088 ms 83692 KB Output is correct
12 Correct 3108 ms 83820 KB Output is correct
13 Correct 3095 ms 85188 KB Output is correct
14 Correct 3049 ms 82364 KB Output is correct
15 Correct 1903 ms 85636 KB Output is correct
16 Correct 1788 ms 86360 KB Output is correct
17 Correct 1948 ms 85156 KB Output is correct
18 Correct 2551 ms 79640 KB Output is correct
19 Correct 2880 ms 80152 KB Output is correct
20 Correct 2924 ms 79684 KB Output is correct
21 Correct 1457 ms 107988 KB Output is correct
22 Correct 1596 ms 107940 KB Output is correct
23 Correct 1523 ms 108004 KB Output is correct
24 Correct 1503 ms 108212 KB Output is correct
25 Correct 2111 ms 90404 KB Output is correct
26 Correct 2062 ms 96396 KB Output is correct
27 Correct 2164 ms 93260 KB Output is correct
28 Correct 1176 ms 97856 KB Output is correct
29 Correct 1080 ms 115092 KB Output is correct
30 Correct 1673 ms 93572 KB Output is correct
31 Correct 1477 ms 100008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 13 ms 12812 KB Output is correct
3 Correct 17 ms 12892 KB Output is correct
4 Correct 13 ms 12812 KB Output is correct
5 Correct 1130 ms 93276 KB Output is correct
6 Correct 1103 ms 95044 KB Output is correct
7 Correct 1274 ms 94248 KB Output is correct
8 Correct 1833 ms 86804 KB Output is correct
9 Correct 1809 ms 85560 KB Output is correct
10 Correct 1883 ms 86304 KB Output is correct
11 Correct 1086 ms 86160 KB Output is correct
12 Correct 1098 ms 86036 KB Output is correct
13 Correct 1034 ms 85988 KB Output is correct
14 Correct 922 ms 86320 KB Output is correct
15 Correct 881 ms 86132 KB Output is correct
16 Correct 1022 ms 85840 KB Output is correct
17 Correct 1043 ms 86444 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9564 KB Output is correct
2 Correct 3 ms 9636 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 15 ms 12776 KB Output is correct
6 Correct 23 ms 13136 KB Output is correct
7 Correct 18 ms 12892 KB Output is correct
8 Correct 23 ms 12972 KB Output is correct
9 Correct 28 ms 12916 KB Output is correct
10 Correct 23 ms 12944 KB Output is correct
11 Correct 22 ms 12940 KB Output is correct
12 Correct 25 ms 12892 KB Output is correct
13 Correct 14 ms 12888 KB Output is correct
14 Correct 15 ms 12948 KB Output is correct
15 Correct 17 ms 12948 KB Output is correct
16 Correct 17 ms 12908 KB Output is correct
17 Correct 18 ms 12892 KB Output is correct
18 Correct 17 ms 12724 KB Output is correct
19 Correct 16 ms 13144 KB Output is correct
20 Correct 16 ms 13144 KB Output is correct
21 Correct 17 ms 13228 KB Output is correct
22 Correct 16 ms 13148 KB Output is correct
23 Correct 17 ms 13036 KB Output is correct
24 Correct 17 ms 13072 KB Output is correct
25 Correct 16 ms 13144 KB Output is correct
26 Correct 18 ms 12892 KB Output is correct
27 Correct 14 ms 13144 KB Output is correct
28 Correct 15 ms 13104 KB Output is correct
29 Correct 14 ms 13916 KB Output is correct
30 Correct 23 ms 12936 KB Output is correct
31 Correct 20 ms 12888 KB Output is correct
32 Correct 20 ms 12892 KB Output is correct
33 Correct 12 ms 13144 KB Output is correct
34 Correct 14 ms 12888 KB Output is correct
35 Correct 13 ms 12892 KB Output is correct
36 Correct 2 ms 9560 KB Output is correct
37 Correct 19 ms 12940 KB Output is correct
38 Correct 20 ms 12916 KB Output is correct
39 Correct 23 ms 12880 KB Output is correct
40 Correct 2164 ms 93392 KB Output is correct
41 Correct 2478 ms 101244 KB Output is correct
42 Correct 2531 ms 105908 KB Output is correct
43 Correct 1909 ms 88336 KB Output is correct
44 Correct 1851 ms 87108 KB Output is correct
45 Correct 2878 ms 83180 KB Output is correct
46 Correct 3088 ms 83692 KB Output is correct
47 Correct 3108 ms 83820 KB Output is correct
48 Correct 3095 ms 85188 KB Output is correct
49 Correct 3049 ms 82364 KB Output is correct
50 Correct 1903 ms 85636 KB Output is correct
51 Correct 1788 ms 86360 KB Output is correct
52 Correct 1948 ms 85156 KB Output is correct
53 Correct 2551 ms 79640 KB Output is correct
54 Correct 2880 ms 80152 KB Output is correct
55 Correct 2924 ms 79684 KB Output is correct
56 Correct 1457 ms 107988 KB Output is correct
57 Correct 1596 ms 107940 KB Output is correct
58 Correct 1523 ms 108004 KB Output is correct
59 Correct 1503 ms 108212 KB Output is correct
60 Correct 2111 ms 90404 KB Output is correct
61 Correct 2062 ms 96396 KB Output is correct
62 Correct 2164 ms 93260 KB Output is correct
63 Correct 1176 ms 97856 KB Output is correct
64 Correct 1080 ms 115092 KB Output is correct
65 Correct 1673 ms 93572 KB Output is correct
66 Correct 1477 ms 100008 KB Output is correct
67 Correct 2 ms 9564 KB Output is correct
68 Correct 13 ms 12812 KB Output is correct
69 Correct 17 ms 12892 KB Output is correct
70 Correct 13 ms 12812 KB Output is correct
71 Correct 1130 ms 93276 KB Output is correct
72 Correct 1103 ms 95044 KB Output is correct
73 Correct 1274 ms 94248 KB Output is correct
74 Correct 1833 ms 86804 KB Output is correct
75 Correct 1809 ms 85560 KB Output is correct
76 Correct 1883 ms 86304 KB Output is correct
77 Correct 1086 ms 86160 KB Output is correct
78 Correct 1098 ms 86036 KB Output is correct
79 Correct 1034 ms 85988 KB Output is correct
80 Correct 922 ms 86320 KB Output is correct
81 Correct 881 ms 86132 KB Output is correct
82 Correct 1022 ms 85840 KB Output is correct
83 Correct 1043 ms 86444 KB Output is correct
84 Correct 2376 ms 87736 KB Output is correct
85 Correct 2320 ms 83612 KB Output is correct
86 Correct 1976 ms 81808 KB Output is correct
87 Correct 3613 ms 82656 KB Output is correct
88 Correct 3526 ms 82564 KB Output is correct
89 Correct 3598 ms 82492 KB Output is correct
90 Correct 3578 ms 82124 KB Output is correct
91 Correct 3592 ms 82224 KB Output is correct
92 Correct 2294 ms 84272 KB Output is correct
93 Correct 2267 ms 84724 KB Output is correct
94 Correct 3162 ms 79868 KB Output is correct
95 Correct 3132 ms 79964 KB Output is correct
96 Correct 3397 ms 79952 KB Output is correct
97 Correct 3275 ms 79408 KB Output is correct
98 Correct 2009 ms 107712 KB Output is correct
99 Correct 1954 ms 107436 KB Output is correct
100 Correct 2045 ms 107164 KB Output is correct
101 Correct 1887 ms 107868 KB Output is correct
102 Correct 2261 ms 84500 KB Output is correct
103 Correct 2141 ms 87492 KB Output is correct
104 Correct 2068 ms 86224 KB Output is correct
105 Correct 1291 ms 89072 KB Output is correct
106 Correct 1464 ms 91792 KB Output is correct
107 Correct 1755 ms 91424 KB Output is correct
108 Correct 1649 ms 90532 KB Output is correct