oj.uz

Submission #730825

# Submission time Handle Problem Language Result Execution time Memory
730825 2023-04-26T13:32:59 Z grogu Two Currencies (JOI23_currencies) C++14
40 / 100
 5000 ms 69224 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define maxn 200005
#define lg 20
int n,m,q;
vector<int> g[maxn];
int in[maxn],out[maxn],st[lg][maxn],ti = 0;
int in2[maxn],out2[maxn],ti2 = 0;
pair<int,int> e[maxn];
vector<pll> v;
void dfs1(int u,int p){
    in[u] = ++ti;
    in2[u] = ++ti2;
    st[0][u] = p;
    for(int s : g[u]){
        if(s==p) continue;
        dfs1(s,u);
    }
    out[u] = ++ti;
    out2[u] = ti2 - 1;
}
bool intree(int x,int y){return in2[y]<=in2[x]&&out2[y]>=out2[x];}
int lca(int x,int y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(int j =  lg-1;j>=0;j--){
        if(!intree(x,st[j][y])) y = st[j][y];
    }
    return st[0][y];
}
struct segtree{
    ll t[2*maxn];
    segtree(){};
    void init(int &v,int tl,int tr){

    }
    ll sum(ll i){
        ll ans = 0;
        for(; i>=0; i = (i&(i+1))-1) ans+=t[i];
        return ans;
    }
    void upd(int v,int tl,int tr,int i,int x){
        for(; i < 2*maxn;i = i|(i+1)) t[i]+=x;
    }
    ll sum(int v,int tl,int tr,int l,int r){
        return sum(r) - sum(l-1);
    }
} tsum,tcnt,tg;
vector<ll> Q[maxn];
int L[maxn],R[maxn],MID[maxn];
int sta[maxn],en[maxn];
int au[maxn];
ll ag[maxn];
int ansl[maxn];
int ansr[maxn];
int rez[maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        e[i] = {x,y};
        g[x].pb(y);
        g[y].pb(x);
    }
    v.pb({-1,-1});
    for(int i = 1;i<=m;i++){
        ll j,w; cin >> j >> w;
        v.pb({w,j});
    }
    sort(all(v));
    dfs1(1,1);
    for(int j = 1;j<lg;j++) for(int i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]];
    for(int i = 1;i<=q;i++) cin >> sta[i] >> en[i] >> au[i] >> ag[i];
    for(int i = 1;i<=q;i++){
        L[i] = 0,R[i] = m;
        ansl[i] = m+1;
        ansr[i] = -llinf;
        rez[i] = 0;
    }
    bool change = 1;
    while(change){
        for(int i = 0;i<=m;i++) Q[i].clear();
        change = 0;
        for(int i = 1;i<=q;i++){
            if(L[i]>R[i]) continue;
            change = 1;
            MID[i] = (L[i] + R[i])/2;
            Q[MID[i]].pb(i);
        }
        //here;
        for(int i = m;i>=0;i--){
            if(v[i].fi!=-1){
                ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
                if(st[0][y]==x) swap(x,y);
                ll w = v[i].fi;
                tg.upd(1,1,ti,in[x],1);
                tg.upd(1,1,ti,out[x],-1);
            }
        }
        //here;
        for(int i = 0;i<=m;i++){
            if(v[i].fi!=-1){
                ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
                if(st[0][y]==x) swap(x,y);
                ll w = v[i].fi;
                //cerr<<"w: "<<x<< " "<<y<< " "<<w<<endl;
                tsum.upd(1,1,ti,in[x],w);
                tsum.upd(1,1,ti,out[x],-w);
                tcnt.upd(1,1,ti,in[x],1);
                tcnt.upd(1,1,ti,out[x],-1);
                tg.upd(1,1,ti,in[x],-1);
                tg.upd(1,1,ti,out[x],1);
            }
            for(int j : Q[i]){
                int x = sta[j],y = en[j];
                int c = au[j];
                ll d = ag[j];
                int z = lca(x,y);
                //cerr<<"LCA: "<<x<< " "<<y<<" "<<z<<endl;
                ll cur = 0;
                int cntg = 0;
                if(z!=x&&z!=y){
                    cur = tsum.sum(1,1,ti,in[z]+1,in[x]) + tsum.sum(1,1,ti,in[z]+1,in[y]);
                    cntg = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]);
                }else{
                    if(x==z) swap(x,y);
                    cur = tsum.sum(1,1,ti,in[z]+1,in[x]);
                    cntg = tg.sum(1,1,ti,in[z]+1,in[x]);
                }
                if(cur<=d){
                    ansr[j] = MID[j];
                    rez[j] = cntg;
                    L[j] = MID[j] + 1;
                }else R[j] = MID[j] - 1;
                //if(j==8) cerr<<"j: "<<x<< " "<<y<< " "<<d<< " "<<cur<<endl;
            }
            Q[i].clear();
        }
        for(int i = 0;i<=m;i++){
            if(v[i].fi!=-1){
                int x = e[v[i].sc].fi,y = e[v[i].sc].sc;
                if(st[0][y]==x) swap(x,y);
                ll w = v[i].fi;
                tsum.upd(1,1,ti,in[x],-w);
                tsum.upd(1,1,ti,out[x],w);
                tcnt.upd(1,1,ti,in[x],-1);
                tcnt.upd(1,1,ti,out[x],1);
            }
        }
    }
    for(int i = 1;i<=q;i++){
        L[i] = 0,R[i] = m;
    }
    change = 1;
    while(change){
        for(int i = 0;i<=m;i++) Q[i].clear();
        change = 0;
        for(int i = 1;i<=q;i++){
            if(L[i]>R[i]) continue;
            change = 1;
            MID[i] = (L[i] + R[i])/2;
            Q[MID[i]].pb(i);
        }
        //here;
        for(int i = m;i>=0;i--){
            if(v[i].fi!=-1){
                int x = e[v[i].sc].fi,y = e[v[i].sc].sc;
                if(st[0][y]==x) swap(x,y);
                ll w = v[i].fi;
                tg.upd(1,1,ti,in[x],1);
                tg.upd(1,1,ti,out[x],-1);
            }
            for(ll j : Q[i]){
                int x = sta[j],y = en[j],c = au[j];
                ll d = ag[j];
                int z = lca(x,y);
                ll cur = 0;
                if(z!=x&&z!=y){
                    cur = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]);
                }else{
                    if(x==z) swap(x,y);
                    cur = tg.sum(1,1,ti,in[z]+1,in[x]);
                }
                if(cur<=c){
                    ansl[j] = MID[j];
                    R[j] = MID[j] - 1;
                }else L[j] = MID[j] + 1;
            }
            Q[i].clear();
        }
        for(int i = m;i>=0;i--){
            if(v[i].fi!=-1){
                ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
                if(st[0][y]==x) swap(x,y);
                ll w = v[i].fi;
                tg.upd(1,1,ti,in[x],-1);
                tg.upd(1,1,ti,out[x],1);
            }
        }
    }
    for(int i = 1;i<=q;i++){
        if(ansl[i]>ansr[i]+1){
            cout<<-1<<endl;
            continue;
        }else cout<<au[i] - rez[i]<<endl;
    }
	return 0;
}
/**
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63
**/

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:95:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
   95 |         ansr[i] = -llinf;
      |                   ^
currencies.cpp:113:20: warning: unused variable 'w' [-Wunused-variable]
  113 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:134:21: warning: unused variable 'c' [-Wunused-variable]
  134 |                 int c = au[j];
      |                     ^
currencies.cpp:187:20: warning: unused variable 'w' [-Wunused-variable]
  187 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:193:20: warning: unused variable 'd' [-Wunused-variable]
  193 |                 ll d = ag[j];
      |                    ^
currencies.cpp:213:20: warning: unused variable 'w' [-Wunused-variable]
  213 |                 ll w = v[i].fi;
      |                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 24 ms 10628 KB Output is correct
6 Correct 27 ms 10828 KB Output is correct
7 Correct 23 ms 10656 KB Output is correct
8 Correct 28 ms 10824 KB Output is correct
9 Correct 29 ms 10788 KB Output is correct
10 Correct 30 ms 10892 KB Output is correct
11 Correct 31 ms 10916 KB Output is correct
12 Correct 29 ms 10856 KB Output is correct
13 Correct 22 ms 10884 KB Output is correct
14 Correct 25 ms 10820 KB Output is correct
15 Correct 26 ms 10836 KB Output is correct
16 Correct 33 ms 10864 KB Output is correct
17 Correct 29 ms 10764 KB Output is correct
18 Correct 28 ms 10864 KB Output is correct
19 Correct 26 ms 10860 KB Output is correct
20 Correct 26 ms 10792 KB Output is correct
21 Correct 26 ms 10836 KB Output is correct
22 Correct 26 ms 10876 KB Output is correct
23 Correct 31 ms 10856 KB Output is correct
24 Correct 27 ms 10788 KB Output is correct
25 Correct 26 ms 10836 KB Output is correct
26 Correct 23 ms 10872 KB Output is correct
27 Correct 22 ms 10880 KB Output is correct
28 Correct 24 ms 10836 KB Output is correct
29 Correct 24 ms 10840 KB Output is correct
30 Correct 31 ms 10808 KB Output is correct
31 Correct 28 ms 10888 KB Output is correct
32 Correct 28 ms 10760 KB Output is correct
33 Correct 20 ms 10880 KB Output is correct
34 Correct 20 ms 10932 KB Output is correct
35 Correct 21 ms 10924 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 28 ms 10796 KB Output is correct
3 Correct 30 ms 10884 KB Output is correct
4 Correct 28 ms 10828 KB Output is correct
5 Correct 3895 ms 48268 KB Output is correct
6 Execution timed out 5009 ms 57336 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 21 ms 10848 KB Output is correct
3 Correct 20 ms 10956 KB Output is correct
4 Correct 22 ms 10964 KB Output is correct
5 Correct 1242 ms 52144 KB Output is correct
6 Correct 1030 ms 55876 KB Output is correct
7 Correct 1399 ms 55276 KB Output is correct
8 Correct 2072 ms 68992 KB Output is correct
9 Correct 2013 ms 68784 KB Output is correct
10 Correct 2045 ms 69000 KB Output is correct
11 Correct 1695 ms 69224 KB Output is correct
12 Correct 1648 ms 69036 KB Output is correct
13 Correct 1606 ms 69092 KB Output is correct
14 Correct 1827 ms 68440 KB Output is correct
15 Correct 1797 ms 68752 KB Output is correct
16 Correct 1853 ms 69124 KB Output is correct
17 Correct 1876 ms 68912 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 24 ms 10628 KB Output is correct
6 Correct 27 ms 10828 KB Output is correct
7 Correct 23 ms 10656 KB Output is correct
8 Correct 28 ms 10824 KB Output is correct
9 Correct 29 ms 10788 KB Output is correct
10 Correct 30 ms 10892 KB Output is correct
11 Correct 31 ms 10916 KB Output is correct
12 Correct 29 ms 10856 KB Output is correct
13 Correct 22 ms 10884 KB Output is correct
14 Correct 25 ms 10820 KB Output is correct
15 Correct 26 ms 10836 KB Output is correct
16 Correct 33 ms 10864 KB Output is correct
17 Correct 29 ms 10764 KB Output is correct
18 Correct 28 ms 10864 KB Output is correct
19 Correct 26 ms 10860 KB Output is correct
20 Correct 26 ms 10792 KB Output is correct
21 Correct 26 ms 10836 KB Output is correct
22 Correct 26 ms 10876 KB Output is correct
23 Correct 31 ms 10856 KB Output is correct
24 Correct 27 ms 10788 KB Output is correct
25 Correct 26 ms 10836 KB Output is correct
26 Correct 23 ms 10872 KB Output is correct
27 Correct 22 ms 10880 KB Output is correct
28 Correct 24 ms 10836 KB Output is correct
29 Correct 24 ms 10840 KB Output is correct
30 Correct 31 ms 10808 KB Output is correct
31 Correct 28 ms 10888 KB Output is correct
32 Correct 28 ms 10760 KB Output is correct
33 Correct 20 ms 10880 KB Output is correct
34 Correct 20 ms 10932 KB Output is correct
35 Correct 21 ms 10924 KB Output is correct
36 Correct 5 ms 9940 KB Output is correct
37 Correct 28 ms 10796 KB Output is correct
38 Correct 30 ms 10884 KB Output is correct
39 Correct 28 ms 10828 KB Output is correct
40 Correct 3895 ms 48268 KB Output is correct
41 Execution timed out 5009 ms 57336 KB Time limit exceeded
42 Halted 0 ms 0 KB -