Submission #854046

#	Time	Username	Problem	Language	Result	Execution time	Memory
854046		12345678	Two Currencies (JOI23_currencies)	C++17	100 / 100	641 ms	143552 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=17;
ll n, m, q, u, v, p, c, lvl[nx], pa[nx][kx], sp, tp, x, y;
vector<pair<ll, ll>> d[nx], t, s[nx];
bool vs[nx];

void dfs(int u, int p)
{
    pa[u][0]=p; lvl[u]=lvl[p]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, idx]:d[u]) if (v!=p) dfs(v, u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[u]<=lvl[pa[v][i]]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

struct persist
{
    struct node
    {
        ll sm, f;
        node *l, *r;
        node(): sm(0), f(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &t)
    {
        t=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, t->l);
        build(md+1, r, t->r);
        t->f=t->l->f+t->r->f;
        t->sm=t->l->sm+t->r->sm;
    }
    void update(int l, int r, pnode &t, pnode k, int idx, ll val)
    {
        t=new node(*k);
        if (l==r) return t->f=1, t->sm=val, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, t->l, k->l, idx, val);
        else update(md+1, r, t->r, k->r, idx, val);
        t->f=t->l->f+t->r->f;
        t->sm=t->l->sm+t->r->sm;
    }
    ll query(int l, int r, pnode s, pnode t, pnode lc, ll am)
    {
        //printf("%d %d %d\n", l, r, am);
        if (l==r) return (s->sm+t->sm-2*lc->sm<=am)?(s->f+t->f-2*lc->f):0;
        int md=(l+r)/2;
        ll usel=s->l->sm+t->l->sm-2*(lc->l->sm);
        if (usel<=am) return s->l->f+t->l->f-2*lc->l->f+query(md+1, r, s->r, t->r, lc->r, am-usel);
        return query(l, md, s->l, t->l, lc->l, am);
    }
} st;

void dfs2(int u, int p)
{
    for (auto [v, idx]:d[u])
    {
        if (v==p) continue;
        st.rt[v]=st.rt[u];
        for (auto [vl, idx2]:s[idx]) st.update(1, m, st.rt[v], st.rt[v], idx2, vl);
        dfs2(v, u);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=n-1; i++) cin>>u>>v, d[u].push_back({v, i}), d[v].push_back({u, i});
    for (int i=1; i<=m; i++) cin>>p>>c, t.push_back({c, p});
    sort(t.begin(), t.end());
    for (int i=0; i<m; i++) s[t[i].second].push_back({t[i].first, i+1});
    dfs(1, 1);
    st.build(1, m, st.rt[1]);
    dfs2(1, 1);
    while (q--)
    {
        cin>>sp>>tp>>x>>y;
        int lc=lca(sp, tp);
        //printf("%d %d %d\n", st.rt[sp], st.rt[tp], st.rt[lc]);
        ll gu=st.query(1, m, st.rt[sp], st.rt[tp], st.rt[lc], y);
        ll tc=st.rt[sp]->f+st.rt[tp]->f-2*st.rt[lc]->f;
        if (tc-gu>x) cout<<-1<<'\n';
        else cout<<x-(tc-gu)<<'\n';
    }
}

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