Submission #1366360

#TimeUsernameProblemLanguageResultExecution timeMemory
1366360hanguyendanghuyTwo Currencies (JOI23_currencies)C++20
0 / 100
2 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
constexpr ll MAXN=2e5+5,MOD=998244353,INF=1e18;
ll n,m,i,j,p,k,t,ans,dem,st,en,dep[MAXN],sz[MAXN],id[MAXN],par[MAXN],chain[MAXN],headchain[MAXN];
ll l[MAXN],r[MAXN],best[MAXN],luu[MAXN],cnt_check_point[MAXN];
vector<ll> adj[MAXN],mid[MAXN];
struct h{
    ll u,v;
} edge[MAXN];
struct mt{
    ll id,val;
} a[MAXN];
struct hymt{
    ll st,en,gold,silver;
} q[MAXN];
bool cmp(mt x,mt y){
    return x.val<y.val;
}
void dfs(ll u,ll pre){
    sz[u]=1;
    for(ll x:adj[u]){
        if(x==pre) continue;
        dep[x]=dep[u]+1;
        par[x]=u;
        dfs(x,u);
        sz[u]+=sz[x];
    }
}
ll cntchain=1,cnt=0;
void hld(ll u){
    if(!headchain[cntchain])
        headchain[cntchain]=u;
    chain[u]=cntchain;
    id[u]=++cnt;
    ll v=-1;
    for(ll x:adj[u])
        if(!chain[x]&&(v==0||sz[x]>sz[v])) v=x;
    if(v>0)
        hld(v);
    for(ll x:adj[u]){
        if(!chain[x]){
            cntchain++;
            hld(x);
        }
    }
}
pair<ll,ll> merge(pair<ll,ll> x,pair<ll,ll> y){
    return {x.fi+y.fi,x.se+y.se};
}
struct seg{
    pair<ll,ll> b[4*MAXN];
    void build(){
        for(ll i=1;i<=4*m;i++)
            b[i]={0,0};
    }
    void update(ll in,ll l,ll r,ll pos,ll val){
        if(l==r){
            b[in]=merge(b[in],{val,1});
        }
        else{
            ll m=(l+r)>>1;
            if(pos<=m)
                update(in*2,l,m,pos,val);
            else update(in*2+1,m+1,r,pos,val);
            b[in]=merge(b[in*2],b[in*2+1]);
        }
    }
    pair<ll,ll> get(ll in,ll l,ll r,ll l1,ll r1){
        if(l>r1||r<l1) return {0,0};
        else if(l>=l1&&r<=r1) return b[in];
        else{
            ll m=(l+r)>>1;
            return merge(get(in*2,l,m,l1,r1),get(in*2+1,m+1,r,l1,r1));
        }
    }
} seg;
pair<ll,ll> get(ll u,ll v){
    pair<ll,ll> val={0,0};
    while(chain[u]!=chain[v]){
        if(chain[u]>chain[v]){
            val=merge(val,seg.get(1,1,n,id[headchain[chain[u]]],id[u]));
            u=par[headchain[chain[u]]];
        }
        else{
            val=merge(val,seg.get(1,1,n,id[headchain[chain[v]]],id[v]));
            v=par[headchain[chain[v]]];
        }
    }
    if(dep[u]>dep[v])
        swap(u,v);
    val=merge(val,seg.get(1,1,n,id[u],id[v]));
    val.fi-=luu[u];
    return val;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("KHOBAU.INP","r",stdin);
    // freopen("KHOBAU.OUT","w",stdout);
    cin>>n>>m>>k;
    for(i=1;i<n;i++){
        cin>>edge[i].u>>edge[i].v;
        adj[edge[i].u].pb(edge[i].v);
        adj[edge[i].v].pb(edge[i].u);
    }
    dfs(1,1);
    hld(1);
    for(i=1;i<n;i++){
        if(dep[edge[i].u]>dep[edge[i].v])
            swap(edge[i].u,edge[i].v);
    }
    for(i=1;i<=m;i++){
        cin>>a[i].id>>a[i].val;
    }
    sort(a+1,a+m+1,cmp);
    vector<ll> b;
    for(i=1;i<=m;i++){
        seg.update(1,1,n,id[edge[a[i].id].v],a[i].val);
    }
    for(i=1;i<=k;i++){
        cin>>q[i].st>>q[i].en>>q[i].gold>>q[i].silver;
        cnt_check_point[i]=get(q[i].st,q[i].en).se;
        l[i]=1,r[i]=m,best[i]=-1;
        b.pb(i);
    }
    while(b.size()){
        vector<ll> c;
        for(ll x:b){
            if(l[x]<=r[x]){
                mid[(l[x]+r[x])>>1].pb(x);
                c.pb(x);
            }
        }
        seg.build();
        for(i=1;i<=n;i++)
            luu[i]=0;
        for(i=1;i<=m;i++){
            seg.update(1,1,n,id[edge[a[i].id].v],a[i].val);
            luu[edge[a[i].id].v]+=a[i].val;
            for(ll x:mid[i]){
                pair<ll,ll> val=get(q[x].st,q[x].en);
                // cout<<x<<" "<<i<<" "<<val.fi<<" "<<val.se<<'\n';
                if(cnt_check_point[x]-val.se<=q[x].gold&&val.fi<=q[x].silver){
                    best[x]=q[x].gold-(cnt_check_point[x]-val.se);
                    l[x]=i+1;
                }
                else r[x]=i-1;
            }
            mid[i].clear();
        }
        swap(b,c);
    }
    for(i=1;i<=k;i++){
        cout<<best[i]<<'\n';
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...