oj.uz

Submission #730826

# Submission time Handle Problem Language Result Execution time Memory
730826 2023-04-26T13:35:47 Z grogu Two Currencies (JOI23_currencies) C++14
40 / 100
 5000 ms 63368 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(au[i]<rez[i]){
            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 10064 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 24 ms 10672 KB Output is correct
6 Correct 28 ms 10792 KB Output is correct
7 Correct 23 ms 10744 KB Output is correct
8 Correct 32 ms 10788 KB Output is correct
9 Correct 34 ms 10724 KB Output is correct
10 Correct 36 ms 10804 KB Output is correct
11 Correct 30 ms 10764 KB Output is correct
12 Correct 29 ms 10800 KB Output is correct
13 Correct 22 ms 10920 KB Output is correct
14 Correct 26 ms 10836 KB Output is correct
15 Correct 27 ms 10852 KB Output is correct
16 Correct 28 ms 10940 KB Output is correct
17 Correct 31 ms 10828 KB Output is correct
18 Correct 30 ms 10792 KB Output is correct
19 Correct 34 ms 10828 KB Output is correct
20 Correct 26 ms 10836 KB Output is correct
21 Correct 28 ms 10880 KB Output is correct
22 Correct 27 ms 10836 KB Output is correct
23 Correct 29 ms 10788 KB Output is correct
24 Correct 25 ms 10836 KB Output is correct
25 Correct 26 ms 10740 KB Output is correct
26 Correct 24 ms 10864 KB Output is correct
27 Correct 28 ms 10836 KB Output is correct
28 Correct 24 ms 10900 KB Output is correct
29 Correct 28 ms 10780 KB Output is correct
30 Correct 29 ms 10768 KB Output is correct
31 Correct 28 ms 10828 KB Output is correct
32 Correct 28 ms 10836 KB Output is correct
33 Correct 21 ms 10836 KB Output is correct
34 Correct 21 ms 10848 KB Output is correct
35 Correct 21 ms 10936 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 32 ms 10772 KB Output is correct
3 Correct 32 ms 10836 KB Output is correct
4 Correct 33 ms 10768 KB Output is correct
5 Correct 4529 ms 48252 KB Output is correct
6 Correct 4501 ms 53304 KB Output is correct
7 Correct 4415 ms 57160 KB Output is correct
8 Correct 4219 ms 49968 KB Output is correct
9 Correct 4157 ms 48964 KB Output is correct
10 Execution timed out 5024 ms 55776 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 87 ms 10924 KB Output is correct
3 Correct 22 ms 10840 KB Output is correct
4 Correct 23 ms 10948 KB Output is correct
5 Correct 1524 ms 52112 KB Output is correct
6 Correct 1594 ms 51944 KB Output is correct
7 Correct 2001 ms 50196 KB Output is correct
8 Correct 2475 ms 63248 KB Output is correct
9 Correct 2561 ms 63152 KB Output is correct
10 Correct 2936 ms 63368 KB Output is correct
11 Correct 1978 ms 63364 KB Output is correct
12 Correct 2320 ms 63288 KB Output is correct
13 Correct 2261 ms 63168 KB Output is correct
14 Correct 2621 ms 62796 KB Output is correct
15 Correct 2712 ms 63024 KB Output is correct
16 Correct 2186 ms 63220 KB Output is correct
17 Correct 2538 ms 62968 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 10064 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 24 ms 10672 KB Output is correct
6 Correct 28 ms 10792 KB Output is correct
7 Correct 23 ms 10744 KB Output is correct
8 Correct 32 ms 10788 KB Output is correct
9 Correct 34 ms 10724 KB Output is correct
10 Correct 36 ms 10804 KB Output is correct
11 Correct 30 ms 10764 KB Output is correct
12 Correct 29 ms 10800 KB Output is correct
13 Correct 22 ms 10920 KB Output is correct
14 Correct 26 ms 10836 KB Output is correct
15 Correct 27 ms 10852 KB Output is correct
16 Correct 28 ms 10940 KB Output is correct
17 Correct 31 ms 10828 KB Output is correct
18 Correct 30 ms 10792 KB Output is correct
19 Correct 34 ms 10828 KB Output is correct
20 Correct 26 ms 10836 KB Output is correct
21 Correct 28 ms 10880 KB Output is correct
22 Correct 27 ms 10836 KB Output is correct
23 Correct 29 ms 10788 KB Output is correct
24 Correct 25 ms 10836 KB Output is correct
25 Correct 26 ms 10740 KB Output is correct
26 Correct 24 ms 10864 KB Output is correct
27 Correct 28 ms 10836 KB Output is correct
28 Correct 24 ms 10900 KB Output is correct
29 Correct 28 ms 10780 KB Output is correct
30 Correct 29 ms 10768 KB Output is correct
31 Correct 28 ms 10828 KB Output is correct
32 Correct 28 ms 10836 KB Output is correct
33 Correct 21 ms 10836 KB Output is correct
34 Correct 21 ms 10848 KB Output is correct
35 Correct 21 ms 10936 KB Output is correct
36 Correct 5 ms 9940 KB Output is correct
37 Correct 32 ms 10772 KB Output is correct
38 Correct 32 ms 10836 KB Output is correct
39 Correct 33 ms 10768 KB Output is correct
40 Correct 4529 ms 48252 KB Output is correct
41 Correct 4501 ms 53304 KB Output is correct
42 Correct 4415 ms 57160 KB Output is correct
43 Correct 4219 ms 49968 KB Output is correct
44 Correct 4157 ms 48964 KB Output is correct
45 Execution timed out 5024 ms 55776 KB Time limit exceeded
46 Halted 0 ms 0 KB -