Submission #730827

#	Time	Username	Problem	Language	Result	Execution time	Memory
730827		grogu	Two Currencies (JOI23_currencies)	C++14	100 / 100	4998 ms	61888 KiB

currencies

#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++){
        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 (stderr)

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];
      |                     ^

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32