Submission #1306443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306443		ender_shayan	Two Currencies (JOI23_currencies)	C++20	100 / 100	472 ms	67276 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <pii, vector<pii>, greater<pii>>


const ll inf = 2e18+7 ;// 998244353 ;// 1e9+9;

const int N=1e5+10,L=18;
int n,m,k,q,pre[N],st[N],en[N],t,pos[N],ans[N],par[N][L],h[N],fenn[N];
vector<pii>g[N];
vector<int>vec[N];
vector<ll>vecc;
pair<pair<pii,int>,pair<int,ll>>A[N];
vector<pair<pii,int>>Q[N],QQ[N];
ll fen[N];
void DFS(int v){
    for(int j=1;j<L;j++)par[v][j]=par[par[v][j-1]][j-1];
    st[v]=++t;
    for(pii pp:g[v])if(pp.F!=par[v][0]){
        int u=pp.F,i=pp.S;
        h[u]=h[v]+1;
        par[u][0]=v;
        pos[i]=u;
        DFS(u);
    }
    en[v]=t;
}
int LCA(int v1,int v2){
    if(h[v1]<h[v2])swap(v1,v2);
    int x=h[v1]-h[v2];
    for(int j=0;j<L;j++)if(x>>j&1)v1=par[v1][j];
    if(v1==v2)return v1;
    for(int j=L-1;j>=0;j--)if(par[v1][j]!=par[v2][j]){
        v1=par[v1][j];
        v2=par[v2][j];
    }
    return par[v1][0];
}
void upd(int i,int x){
    for(;i<=n;i+=i&-i)fen[i]+=x;
}
ll get(int i){
    ll ans=0;
    for(;i>0;i-=i&-i)ans+=fen[i];
    return ans;
}
void updd(int i,int x){
    for(;i<=n;i+=i&-i)fenn[i]+=x;
}
int gett(int i){
    int ans=0;
    for(;i>0;i-=i&-i)ans+=fenn[i];
    return ans;
}
bool check(int j){
    int s=A[j].F.F.F,t=A[j].F.F.S,v=A[j].F.S,g=A[j].S.F;ll c=A[j].S.S;
    ll val=get(s)+get(t)-get(v)*2;
    return (val<=c);
}
void get_res(int j,ll x){
    int s=A[j].F.F.F,t=A[j].F.F.S,v=A[j].F.S,g=A[j].S.F;ll c=A[j].S.S;
    ll val=get(s)+get(t)-get(v)*2;val=c-val;val/=x;
    int tt=gett(s)+gett(t)-gett(v)*2+val;
    ans[j]=g+tt;
}
int main(){
    fast_io
    cin>>n>>m>>q;
    for1(n-1){
        int u,v;cin>>u>>v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    DFS(1);
    vector<pii>vec2;
    for1(m){
        int j,c;cin>>j>>c;j=pos[j];
        pre[st[j]]++;pre[en[j]+1]--;
        vecc.pb(c);
        vec2.pb({j,c});
    }
    for1(n)pre[i]+=pre[i-1];
    vecc.pb(-1);
    sort(all(vecc));vecc.resize(unique(all(vecc))-vecc.begin());
    for(pii p:vec2){
        p.S=lb(all(vecc),p.S)-vecc.begin();
        vec[p.S].pb(p.F);
    }
    for1(q){
        int s,t,g;ll c;cin>>s>>t>>g>>c;
        int v=LCA(s,t);
        s=st[s];t=st[t];v=st[v];
        g=g-pre[s]-pre[t]+pre[v]*2;
        A[i]={{{s,t},v},{g,c}};
        Q[vecc.size()/2].pb({{0,vecc.size()},i});
    }
    for(int _=0;_<L;_++){
        for(int i=0;i<vecc.size();i++){
            for(int v:vec[i]){
                upd(st[v],vecc[i]);
                upd(en[v]+1,-vecc[i]);
            }
            for(pair<pii,int>p:Q[i]){
                int l=p.F.F,r=p.F.S,j=p.S;
                if(check(j))l=i;
                else r=i;
                int mid=(l+r)>>1;
                QQ[mid].pb({{l,r},j});
            }
        }
        memset(fen,0,sizeof(fen));
        for0(vecc.size()){
            swap(QQ[i],Q[i]);
            QQ[i].clear();
        }
    }
    vecc.pb(inf);
    for(int i=0;i<vecc.size()-1;i++){
        for(int v:vec[i]){
            upd(st[v],vecc[i]);
            upd(en[v]+1,-vecc[i]);
            updd(st[v],1);
            updd(en[v]+1,-1);
        }
        for(pair<pii,int>p:Q[i])
            get_res(p.S,vecc[i+1]);
    }
    for1(q)cout<<max(ans[i],-1)<<endl;





}

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