Submission #1115662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115662		sitablechair	Two Currencies (JOI23_currencies)	C++17	0 / 100	6 ms	21364 KiB

currencies

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e5+3;

struct Query {
    int s,t,x,y;
};
int n,m,q,dep[N],par[17][N],l[N],r[N];
int ans[N],tin[N],tout[N],hehesiu[N],tdfs=0;
ll pf[N],val[N];
pair<int,int> e[N],sig[N];
Query qr[N];
vector<int> g[N],mid[N],bidi[N];
vector<pair<int,int>> add[N];

void update(int u,int val) {
    if (u==0) return;
    while(u<=n) {
        pf[u]+=val;
        u+=u&(-u);
    }   
}
ll query(int u) {
    ll siuu=0;
    while(u>0) {
        siuu+=pf[u];
        u-=u&(-u);
    }
    return siuu;
}
void predfs(int u,int p=0) {
    tin[u]=++tdfs;
    for(auto v: g[u])
        if (v!=p) {
            par[0][v]=u;
            dep[v]=dep[u]+1;
            For(i,1,16) par[i][v]=par[i-1][par[i-1][v]];
            predfs(v,u);
        }
    tout[u]=tdfs;
}
int LCA(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dif=dep[u]-dep[v];
    For(i,0,16)
        if (dif>>i&1) u=par[i][u];
    if (u==v) return u;
    ForD(i,16,0)
        if (par[i][u]!=par[i][v]) u=par[i][u],v=par[i][v];
    return par[0][u];
}
ll queryPath(int u,int v) {
    int lca=LCA(u,v);
    return query(tin[u])+query(tin[v])-2*query(tin[lca]);
}
void hahasus() {
    fill(pf,pf+1+n,0);
    fill(val,val+1+n,0);
    For(i,1,m) {
        int u=e[sig[i].ss].ff;
        update(tin[u],1);
        update(tout[u]+1,-1);
    }
    For(i,1,q) hehesiu[i]=queryPath(qr[i].s,qr[i].t);
}
void binSearch() {
    while(true) {
        bool skibidi=1;
        For(i,1,q) skibidi&=(l[i]==r[i]);
        if (skibidi) break;
        fill(pf,pf+1+n,0);
        For(i,0,m) mid[i].clear();
        For(i,1,q) mid[l[i]+(r[i]-l[i]+1)/2].pb(i);
        for(auto el: mid[0]) l[el]=0;
        For(i,1,m) {
            int u=e[sig[i].ss].ff;
            update(tin[u],sig[i].ff);
            update(tout[u]+1,-sig[i].ff);
            for(auto el: mid[i]) {
                if (queryPath(qr[el].s,qr[el].t)<=qr[el].y) l[el]=i;
                else r[el]=i-1;
            }
        }
    }
    For(i,1,q) bidi[l[i]].pb(i);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    For(i,1,n-1) {
        cin >> e[i].ff >> e[i].ss;
        g[e[i].ff].pb(e[i].ss);
        g[e[i].ss].pb(e[i].ff);
    }
    predfs(1);
    For(i,1,n-1)
        if (dep[e[i].ff]<dep[e[i].ss]) swap(e[i].ff,e[i].ss);
    For(i,1,m) cin >> sig[i].ss >> sig[i].ff;
    sort(sig+1,sig+1+m);
    For(i,1,q) {
        cin >> qr[i].s >> qr[i].t >> qr[i].x >> qr[i].y;
        l[i]=0;
        r[i]=m;
    }
    binSearch();
    hahasus();
    fill(pf,pf+1+n,0);
    For(i,0,m) {
        if (i) {
            int u=e[sig[i].ss].ff;
            update(tin[u],1);
            update(tout[u]+1,-1);
        }
        for(auto el: bidi[i]) {
            ans[el]=max(qr[el].x-(hehesiu[el]-queryPath(qr[el].s,qr[el].t)),-1LL);
        }
    }
    For(i,1,q) cout << ans[i] << endl;
    return 0;
}

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