Submission #827556

#	Time	Username	Problem	Language	Result	Execution time	Memory
827556		Hanksburger	Two Currencies (JOI23_currencies)	C++17	100 / 100	592 ms	54968 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
long long par[100005][20], edge[100005], depth[100005], in[100005], out[100005], l1[100005], r1[100005], l2[100005], r2[100005], x[100005], y[100005], ans[100005], bit[200005], bit2[200005], n, m, q, sz;
vector<pair<long long, long long> > adj[100005], upd;
void dfs(long long u, long long p)
{
    par[u][0]=p;
    for (long long i=1; i<20; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i].first, w=adj[u][i].second;
        if (v==p)
            continue;
        depth[v]=depth[u]+1;
        edge[v]=w;
        in[w]=(++sz);
        dfs(v, u);
        out[w]=(++sz);
    }
}
void update(long long s, long long t)
{
    for (long long i=s; i<=sz; i+=i&(-i))
    {
        bit[i]+=t;
        if (t>0)
            bit2[i]++;
        else
            bit2[i]--;
    }
}
long long query(long long s)
{
    long long res=0;
    for (long long i=s; i>=1; i-=i&(-i))
        res+=bit[i];
    return res;
}
long long query2(long long s)
{
    long long res=0;
    for (long long i=s; i>=1; i-=i&(-i))
        res+=bit2[i];
    return res;
}
void recur(long long L, long long R, vector<long long> vec)
{
    if (L==R)
    {
        for (long long ind:vec)
        {
            long long res=query2(r1[ind])-query2(l1[ind]-1);
            if (l2[ind])
                res+=query2(r2[ind])-query2(l2[ind]-1);
            ans[ind]=res;
        }
        return;
    }
    long long mid=(L+R+1)/2;
    for (long long i=L; i<mid; i++)
    {
        update(in[upd[i].second], upd[i].first);
        update(out[upd[i].second], -upd[i].first);
    }
    vector<long long> ok, notok;
    for (long long ind:vec)
    {
        long long res=query(r1[ind])-query(l1[ind]-1);
        if (l2[ind])
            res+=query(r2[ind])-query(l2[ind]-1);
        if (res<=y[ind])
            ok.push_back(ind);
        else
            notok.push_back(ind);
    }
    if (ok.size())
        recur(mid, R, ok);
    for (long long i=L; i<mid; i++)
    {
        update(in[upd[i].second], -upd[i].first);
        update(out[upd[i].second], upd[i].first);
    }
    if (notok.size())
        recur(L, mid-1, notok);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for (long long i=1; i<n; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 1);
    for (long long i=0; i<m; i++)
    {
        long long s, t;
        cin >> s >> t;
        upd.push_back({t, s});
    }
    sort(upd.begin(), upd.end());
    for (long long i=1; i<=q; i++)
    {
        long long a, b, curA, curB;
        cin >> a >> b >> x[i] >> y[i];
        if (depth[a]<depth[b])
            swap(a, b);
        curA=a, curB=b;
        if (depth[a]>depth[b])
        {
            for (long long j=19; j>=0; j--)
                if ((depth[a]-depth[b]-1)&(1<<j))
                    curA=par[curA][j];
            if (par[curA][0]==curB)
            {
                l1[i]=in[edge[curA]];
                r1[i]=in[edge[a]];
                l2[i]=-1;
                continue;
            }
            curA=par[curA][0];
        }
        for (long long j=19; j>=0; j--)
        {
            if (par[curA][j]!=par[curB][j])
            {
                curA=par[curA][j];
                curB=par[curB][j];
            }
        }
        l1[i]=in[edge[curA]];
        r1[i]=in[edge[a]];
        l2[i]=in[edge[curB]];
        r2[i]=in[edge[b]];
    }
    vector<long long> tmp;
    for (long long i=1; i<=q; i++)
        tmp.push_back(i);
    recur(0, m, tmp);
    for (long long i=0; i<m; i++)
    {
        update(in[upd[i].second], upd[i].first);
        update(out[upd[i].second], -upd[i].first);
    }
    for (long long i=1; i<=q; i++)
    {
        long long res=query2(r1[i])-query2(l1[i]-1);
        if (l2[i])
            res+=query2(r2[i])-query2(l2[i]-1);
        cout << max(-1LL, x[i]-(res-ans[i])) << '\n';
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:10:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~

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