Submission #1084356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084356		Bananabread	Two Currencies (JOI23_currencies)	C++17	100 / 100	1506 ms	62808 KiB

currencies

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll fenwick[2][100001];
ll sz[100001];
ll pos[100001];
ll depth[100001];
ll up[100001][20];
ll t;
ll n,m,q;
vector<ll> adj[100001];
struct edge{
    ll u,v;
} edges[100001];
struct add{
    ll p,w;
    bool operator < (const add &other){
        return w < other.w;
    }
} add[100001];
struct query{
    ll s,t,x,y,l,r,ans,numroad,lca;
} queries[100001];
vector<ll> sweep[100001];
void dfs(ll u=1,ll par=0){
    up[u][0]=par;
    for(int i=1;i<20;i++){
        up[u][i]=up[up[u][i-1]][i-1];
    }
    depth[u]=depth[par]+1;
    pos[u]=++t;
    for(auto v:adj[u]){
        if(v==par) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
    sz[u]++;
}
ll lca(ll u,ll v){
    if(depth[u]<depth[v]) swap(u,v);
    ll k=depth[u]-depth[v];
    for(int i=19;i>=0;i--){
        if(k&(1<<i)) u=up[u][i];
    }
    if(u==v) return u;
    for(int i=19;i>=0;i--){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
void upd(ll u,ll val){
    for(;u<=n;u+=u&-u){
        if(val>0){
            fenwick[0][u]+=val;
            fenwick[1][u]++;
        }
        else{
            fenwick[0][u]+=val;
            fenwick[1][u]--;
        }
    }
}
ll get(ll u,ll type){
    ll val=0;
    for(;u>0;u-=u&-u){
        val+=fenwick[type][u];
    }
    return val;
}
void proc(){
    for(int i=1;i<=m;i++){
        ll p=add[i].p,w=add[i].w;
        upd(pos[edges[p].u],w);
        upd(pos[edges[p].u]+sz[edges[p].u],-w);
        for(auto po:sweep[i]){
            auto &[u,v,x,y,l,r,ans,numroad,lc]=queries[po];
            lc=lca(u,v);
            ll val=get(pos[u],0)+get(pos[v],0)-2*get(pos[lc],0);
            ll num=get(pos[u],1)+get(pos[v],1)-2*get(pos[lc],1);
            if(val<=y){
                if(x>=numroad-num){
                    ans=max(ans,x-(numroad-num));
                }
                l=i+1;
            }
            else{
                r=i-1;
            }
        }
        sweep[i]={};
    }
    for(int i=1;i<=n;i++){
        fenwick[0][i]=fenwick[1][i]=0;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges[i]={a,b};
    }
    dfs();
    for(int i=1;i<=n;i++){
        ll &u=edges[i].u;
        ll &v=edges[i].v;
        if(depth[u]<depth[v]) swap(u,v);
    }
    for(int i=1;i<=m;i++){
        ll p,w;
        cin>>p>>w;
        add[i]={p,w};
    }
    sort(add+1,add+m+1);
    for(int i=1;i<=q;i++){
        ll s,t,x,y;
        cin>>s>>t>>x>>y;
        queries[i]={s,t,x,y,1,m,-1,0,lca(s,t)};
    }
    for(int i=1;i<=m;i++){
        ll u=edges[add[i].p].u;
        upd(pos[u],add[i].w);
        upd(pos[u]+sz[u],-add[i].w);
    }
    for(int i=1;i<=q;i++){
        ll u=queries[i].s;
        ll v=queries[i].t;
        ll l=lca(u,v);
        ll num=get(pos[u],1)+get(pos[v],1)-2*get(pos[l],1);
        queries[i].numroad=num;
        if(queries[i].x>=num) queries[i].ans=queries[i].x-num;
    }
    for(int i=1;i<=n;i++){
        fenwick[0][i]=fenwick[1][i]=0;
    }
    while(true){
        ll flag=1;
        for(int i=1;i<=q;i++){
            if(queries[i].r<queries[i].l) continue;
            flag=0;
            ll mid=(queries[i].l+queries[i].r)/2;
            sweep[mid].push_back(i);
        }
        if(flag) break;
        proc();
    }
    for(int i=1;i<=q;i++) cout<<queries[i].ans<<ntr;
}

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