oj.uz

Submission #730824

# Submission time Handle Problem Language Result Execution time Memory
730824 2023-04-26T13:30:14 Z grogu Two Currencies (JOI23_currencies) C++14
10 / 100
 5000 ms 55872 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];
    int ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
    segtree(){};
    void init(int &v,int tl,int tr){
        if(!v) v = ++tsz;
        if(tl==tr) return;
        int mid = (tl+tr)/2;
        init(ls[v],tl,mid);
        init(rs[v],mid+1,tr);
    }
    void upd(int v,int tl,int tr,int i,int x){
        if(tl==tr){t[v]+=x;return;}
        int mid = (tl+tr)/2;
        if(i<=mid) upd(ls[v],tl,mid,i,x);
        else upd(rs[v],mid+1,tr,i,x);
        t[v] = t[ls[v]] + t[rs[v]];
    }
    ll sum(int v,int tl,int tr,int l,int r){
        if(l>r||l>tr||tl>tr||tl>r) return 0;
        if(tl>=l&&tr<=r) return t[v];
        int mid = (tl+tr)/2;
        return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
    }
} 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);
    tsum.init(tsum.root,1,ti);
    tcnt.init(tcnt.root,1,ti);
    tg.init(tg.root,1,ti);
    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:105:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
  105 |         ansr[i] = -llinf;
      |                   ^
currencies.cpp:123:20: warning: unused variable 'w' [-Wunused-variable]
  123 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:144:21: warning: unused variable 'c' [-Wunused-variable]
  144 |                 int c = au[j];
      |                     ^
currencies.cpp:197:20: warning: unused variable 'w' [-Wunused-variable]
  197 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:203:20: warning: unused variable 'd' [-Wunused-variable]
  203 |                 ll d = ag[j];
      |                    ^
currencies.cpp:223:20: warning: unused variable 'w' [-Wunused-variable]
  223 |                 ll w = v[i].fi;
      |                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 60 ms 10820 KB Output is correct
6 Correct 70 ms 10980 KB Output is correct
7 Correct 56 ms 10816 KB Output is correct
8 Correct 73 ms 11064 KB Output is correct
9 Correct 82 ms 11040 KB Output is correct
10 Correct 83 ms 11056 KB Output is correct
11 Correct 90 ms 11072 KB Output is correct
12 Correct 77 ms 10980 KB Output is correct
13 Correct 60 ms 11072 KB Output is correct
14 Correct 70 ms 11220 KB Output is correct
15 Correct 70 ms 11096 KB Output is correct
16 Correct 70 ms 10992 KB Output is correct
17 Correct 72 ms 11024 KB Output is correct
18 Correct 75 ms 11012 KB Output is correct
19 Correct 75 ms 11052 KB Output is correct
20 Correct 74 ms 11232 KB Output is correct
21 Correct 73 ms 11104 KB Output is correct
22 Correct 77 ms 11084 KB Output is correct
23 Correct 60 ms 11096 KB Output is correct
24 Correct 76 ms 11020 KB Output is correct
25 Correct 67 ms 11084 KB Output is correct
26 Correct 61 ms 11032 KB Output is correct
27 Correct 64 ms 11052 KB Output is correct
28 Correct 91 ms 11112 KB Output is correct
29 Correct 58 ms 11072 KB Output is correct
30 Correct 71 ms 11044 KB Output is correct
31 Correct 79 ms 11096 KB Output is correct
32 Correct 73 ms 11092 KB Output is correct
33 Correct 57 ms 11064 KB Output is correct
34 Correct 61 ms 11164 KB Output is correct
35 Correct 56 ms 11168 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 71 ms 11008 KB Output is correct
3 Correct 72 ms 11028 KB Output is correct
4 Correct 71 ms 11084 KB Output is correct
5 Execution timed out 5080 ms 51960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 60 ms 11040 KB Output is correct
3 Correct 58 ms 11060 KB Output is correct
4 Correct 56 ms 11128 KB Output is correct
5 Execution timed out 5042 ms 55872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 60 ms 10820 KB Output is correct
6 Correct 70 ms 10980 KB Output is correct
7 Correct 56 ms 10816 KB Output is correct
8 Correct 73 ms 11064 KB Output is correct
9 Correct 82 ms 11040 KB Output is correct
10 Correct 83 ms 11056 KB Output is correct
11 Correct 90 ms 11072 KB Output is correct
12 Correct 77 ms 10980 KB Output is correct
13 Correct 60 ms 11072 KB Output is correct
14 Correct 70 ms 11220 KB Output is correct
15 Correct 70 ms 11096 KB Output is correct
16 Correct 70 ms 10992 KB Output is correct
17 Correct 72 ms 11024 KB Output is correct
18 Correct 75 ms 11012 KB Output is correct
19 Correct 75 ms 11052 KB Output is correct
20 Correct 74 ms 11232 KB Output is correct
21 Correct 73 ms 11104 KB Output is correct
22 Correct 77 ms 11084 KB Output is correct
23 Correct 60 ms 11096 KB Output is correct
24 Correct 76 ms 11020 KB Output is correct
25 Correct 67 ms 11084 KB Output is correct
26 Correct 61 ms 11032 KB Output is correct
27 Correct 64 ms 11052 KB Output is correct
28 Correct 91 ms 11112 KB Output is correct
29 Correct 58 ms 11072 KB Output is correct
30 Correct 71 ms 11044 KB Output is correct
31 Correct 79 ms 11096 KB Output is correct
32 Correct 73 ms 11092 KB Output is correct
33 Correct 57 ms 11064 KB Output is correct
34 Correct 61 ms 11164 KB Output is correct
35 Correct 56 ms 11168 KB Output is correct
36 Correct 5 ms 9940 KB Output is correct
37 Correct 71 ms 11008 KB Output is correct
38 Correct 72 ms 11028 KB Output is correct
39 Correct 71 ms 11084 KB Output is correct
40 Execution timed out 5080 ms 51960 KB Time limit exceeded
41 Halted 0 ms 0 KB -