oj.uz

Submission #730820

# Submission time Handle Problem Language Result Execution time Memory
730820 2023-04-26T13:22:41 Z grogu Two Currencies (JOI23_currencies) C++14
0 / 100
 5000 ms 78896 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
ll n,m,q;
vector<ll> g[maxn];
ll in[maxn],out[maxn],st[lg][maxn],ti = 0;
ll in2[maxn],out2[maxn],ti2 = 0;
pll e[maxn];
vector<pll> v;
void dfs1(ll u,ll p){
    in[u] = ++ti;
    in2[u] = ++ti2;
    st[0][u] = p;
    for(ll s : g[u]){
        if(s==p) continue;
        dfs1(s,u);
    }
    out[u] = ++ti;
    out2[u] = ti2 - 1;
}
bool intree(ll x,ll y){return in2[y]<=in2[x]&&out2[y]>=out2[x];}
ll lca(ll x,ll y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(ll 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],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
    segtree(){};
    void init(ll &v,ll tl,ll tr){
        if(!v) v = ++tsz;
        if(tl==tr) return;
        ll mid = (tl+tr)/2;
        init(ls[v],tl,mid);
        init(rs[v],mid+1,tr);
    }
    void upd(ll v,ll tl,ll tr,ll i,ll x){
        if(tl==tr){t[v]+=x;return;}
        ll 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(ll v,ll tl,ll tr,ll l,ll r){
        if(l>r||l>tr||tl>tr||tl>r) return 0;
        if(tl>=l&&tr<=r) return t[v];
        ll 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];
ll L[maxn],R[maxn],MID[maxn];
ll sta[maxn],en[maxn],au[maxn],ag[maxn];
ll ansl[maxn];
ll ansr[maxn];
ll rez[maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m >> q;
    for(ll 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(ll 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(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]];
    for(ll i = 1;i<=q;i++) cin >> sta[i] >> en[i] >> au[i] >> ag[i];
    for(ll i = 1;i<=q;i++){
        L[i] = 0,R[i] = m;
        ansl[i] = llinf;
        ansr[i] = -llinf;
        rez[i] = 0;
    }
    bool change = 1;
    while(change){
        for(ll i = 0;i<=m;i++) Q[i].clear();
        change = 0;
        for(ll 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(ll 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(ll 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(ll j : Q[i]){
                ll x = sta[j],y = en[j],c = au[j],d = ag[j];
                ll z = lca(x,y);
                //cerr<<"LCA: "<<x<< " "<<y<<" "<<z<<endl;
                ll cur = 0;
                ll 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(ll 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;
                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(ll i = 1;i<=q;i++){
        L[i] = 0,R[i] = m;
    }
    change = 1;
    while(change){
        for(ll i = 0;i<=m;i++) Q[i].clear();
        change = 0;
        for(ll 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(ll 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(ll j : Q[i]){
                ll x = sta[j],y = en[j],c = au[j],d = ag[j];
                ll 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(ll 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(ll 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:120:20: warning: unused variable 'w' [-Wunused-variable]
  120 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:140:41: warning: unused variable 'c' [-Wunused-variable]
  140 |                 ll x = sta[j],y = en[j],c = au[j],d = ag[j];
      |                                         ^
currencies.cpp:192:20: warning: unused variable 'w' [-Wunused-variable]
  192 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:197:51: warning: unused variable 'd' [-Wunused-variable]
  197 |                 ll x = sta[j],y = en[j],c = au[j],d = ag[j];
      |                                                   ^
currencies.cpp:217:20: warning: unused variable 'w' [-Wunused-variable]
  217 |                 ll w = v[i].fi;
      |                    ^

Subtask #1
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 6 ms 9940 KB Output is correct
4 Correct 6 ms 9988 KB Output is correct
5 Correct 65 ms 11316 KB Output is correct
6 Correct 75 ms 11568 KB Output is correct
7 Correct 60 ms 11292 KB Output is correct
8 Correct 92 ms 11648 KB Output is correct
9 Correct 101 ms 11644 KB Output is correct
10 Correct 85 ms 11620 KB Output is correct
11 Correct 80 ms 11620 KB Output is correct
12 Correct 81 ms 11608 KB Output is correct
13 Correct 72 ms 11740 KB Output is correct
14 Correct 78 ms 11648 KB Output is correct
15 Correct 74 ms 11592 KB Output is correct
16 Correct 81 ms 11652 KB Output is correct
17 Correct 78 ms 11652 KB Output is correct
18 Correct 93 ms 11704 KB Output is correct
19 Correct 79 ms 11736 KB Output is correct
20 Correct 78 ms 11596 KB Output is correct
21 Incorrect 78 ms 11692 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10000 KB Output is correct
2 Correct 74 ms 11500 KB Output is correct
3 Correct 90 ms 11656 KB Output is correct
4 Correct 88 ms 11676 KB Output is correct
5 Execution timed out 5101 ms 76952 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 64 ms 11596 KB Output is correct
3 Correct 74 ms 11672 KB Output is correct
4 Correct 72 ms 11724 KB Output is correct
5 Execution timed out 5032 ms 78896 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 6 ms 9940 KB Output is correct
4 Correct 6 ms 9988 KB Output is correct
5 Correct 65 ms 11316 KB Output is correct
6 Correct 75 ms 11568 KB Output is correct
7 Correct 60 ms 11292 KB Output is correct
8 Correct 92 ms 11648 KB Output is correct
9 Correct 101 ms 11644 KB Output is correct
10 Correct 85 ms 11620 KB Output is correct
11 Correct 80 ms 11620 KB Output is correct
12 Correct 81 ms 11608 KB Output is correct
13 Correct 72 ms 11740 KB Output is correct
14 Correct 78 ms 11648 KB Output is correct
15 Correct 74 ms 11592 KB Output is correct
16 Correct 81 ms 11652 KB Output is correct
17 Correct 78 ms 11652 KB Output is correct
18 Correct 93 ms 11704 KB Output is correct
19 Correct 79 ms 11736 KB Output is correct
20 Correct 78 ms 11596 KB Output is correct
21 Incorrect 78 ms 11692 KB Output isn't correct
22 Halted 0 ms 0 KB -