Submission #917077

#	Time	Username	Problem	Language	Result	Execution time	Memory
917077		manizare	Two Currencies (JOI23_currencies)	C++14	100 / 100	3055 ms	68568 KiB

currencies

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")


#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n"; 

using namespace std ;   
const int maxn = 1e5 + 10 ,  mod = 1e9 + 7 , inf =1e9 , lg = 19  ;
int fen[maxn],par[maxn][lg+1],dis[maxn],pai[maxn],l[maxn],r[maxn],x[maxn],y[maxn],V[maxn],U[maxn],st[maxn],en[maxn];
int cnt=1, n , m , q,ans[maxn];
vector <int> vec[maxn] ;
vector <pii> ed, G[maxn];

void upd(int x, int w){
    while(x<=n){
        fen[x] += w; 
        x+=x&-x;
    }
}
int que(int v){
    int ans =0 ;
    while(v){
        ans += fen[v] ;
        v-=v&-v ;
    }
    return ans ;
}
int up(int v ,int d){
    rep(i ,0,lg)if(d>>i&1)v= par[v][i] ;
    return v ;
}
int lca(int v,int u){
    if(dis[v] < dis[u])swap(v,u);
    v=up(v,dis[v]-dis[u]);
    per(i , lg ,0 ){
        if(par[v][i]!=par[u][i])v = par[v][i] , u = par[u][i] ;
    }
    if(v==u)return v;
    return par[v][0] ;
}

void d1(int v, int p =0){
    par[v][0] = p; 
    rep(i , 1,lg){
        par[v][i] = par[par[v][i-1]][i-1] ;
    }
    st[v] = cnt ;cnt++;
    for(pii u : G[v]){
        if(u.F == p)continue ;
        pai[u.S] = u.F ;
        dis[u.F] = dis[v]+1 ;
        d1(u.F , v) ;
    }
    en[v] = cnt-1 ;
}


signed main(){
    ios::sync_with_stdio(0) ;cin.tie(0);
     cin >> n >> m >> q; 
    rep(i , 1 , n-1){
        int v,u ;
        cin >> v >> u ;
        G[v].pb({u ,i});
        G[u].pb({v,i}) ;
    }
    d1(1); 
    rep(i , 1, m){
        int id , w ;
        cin >> id >> w ;
        ed.pb({w,id}) ;
    }    
    sort(all(ed));
    rep(i , 1, q){
        cin >> V[i] >> U[i] >> x[i] >> y[i] ;
        l[i] = -1 ;
        r[i] =sz(ed) ;
    }
    rep(i , 0 , lg){
        rep(i , 1,q){
            vec[(l[i]+r[i])/2].pb(i);
        }
        rep(i , 0 , sz(ed)-1){
            int v =pai[ed[i].S] , w = ed[i].F ;
            upd(st[v] , w);upd(en[v]+1,-w);
            for(int id : vec[i]){
                if(que(st[V[id]]) + que(st[U[id]]) - 2*que(st[lca(V[id] , U[id])]) <= y[id]){
                    l[id] = i ;
                }else{
                    r[id] = i ;
                }
            }
        }
        rep(j , 0 , max(n , sz(ed))){
            fen[j] =0 ;
            vec[j].clear() ;
        }
    }
    rep(i , 1 , q){
        vec[l[i]+1].pb(i) ;
    }
    per(i , sz(ed) , 0){
        for(int id : vec[i]){
            ans[id] = que(st[V[id]]) + que(st[U[id]]) - 2*que(st[lca(V[id] , U[id])]) ;
        }
        if(i ==0 )continue ;
        int v=pai[ed[i-1].S] , w = ed[i-1].F ;
        upd(st[v] , 1) ; upd(en[v]+1, -1) ;
    }
    rep(i , 1, q){
        if(ans[i] > x[i]){
            cout << "-1\n";
        }else{
            cout << x[i]-ans[i] << "\n"; 
        }
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:116:32: warning: unused variable 'w' [-Wunused-variable]
  116 |         int v=pai[ed[i-1].S] , w = ed[i-1].F ;
      |                                ^

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