Submission #893214

#	Time	Username	Problem	Language	Result	Execution time	Memory
893214		VerdantGMD	Two Currencies (JOI23_currencies)	C++17	100 / 100	1117 ms	56788 KiB

currencies

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
vector<pair<int, int> > tab[100005];
vector<pair<int, int> > adds;
vector<int> mids[100005];
struct query
{
    int l;
    int r;
    int mid;
    int lca;
    int a;
    int b;
    int gold;
    int wyn;
    long long silver;
    int coinsatloss = 0;
};

vector<query> queries;
int jp[100005][21];
int checked[100006];
int timee = 1;
int preorder[100005];
int postorder[100005];
pair<long long, int> tree[500005];
int base;
int vfe[100005];

void dfs(int p, int parent)
{
    preorder[p] = timee;
    timee++;
    for(int i = 0; i < tab[p].size(); i++)
    {
        if(tab[p][i].first != parent)
        {
            vfe[tab[p][i].second] = tab[p][i].first;
            checked[tab[p][i].first] = checked[p] + 1;

            jp[tab[p][i].first][0] = p;
            for(int o = 1; (1 << o) <= checked[tab[p][i].first]; o++)
            {
                jp[tab[p][i].first][o] = jp[ jp[tab[p][i].first] [o-1] ][o - 1];
            }

            dfs(tab[p][i].first, p);
        }
    }
    postorder[p] = timee;
    timee++;
}

void upd(int a, int val, int add)
{
    a += base;
    tree[a].first += val;
    tree[a].second += add;
    a/=2;
    while(a != 0)
    {
        tree[a].first = tree[a*2].first + tree[a*2+1].first;
        tree[a].second = tree[a*2].second + tree[a*2+1].second;
        a/=2;
    }
}

long long treequery(int a, int b)
{
    a += base - 1;
    b += base + 1;
    long long res = 0 ;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            res += tree[a+1].first;
        }
        if(b % 2 == 1)
        {
            res += tree[b-1].first;
        }
        a/=2;
        b/=2;
    }
    return res;
}

int treequeryamount(int a, int b)
{
    a += base - 1;
    b += base + 1;
    int res = 0 ;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            res += tree[a+1].second;
        }
        if(b % 2 == 1)
        {
            res += tree[b-1].second;
        }
        a/=2;
        b/=2;
    }
    return res;
}

int LCA(int a, int b)
{
    if(checked[b] > checked[a])
    {
        swap(a, b);
    }
    for(int i = 20; i >= 0; i--)
    {
        if(checked[a] - checked[b] >= (1 << i))
        {
            a = jp[a][i];
        }
    }
    if(a == b)
    {
        return a;
    }
    for(int i = 20; i >= 0; i--)
    {
        if(jp[a][i] != jp[b][i])
        {
            a = jp[a][i];
            b = jp[b][i];
        }
    }
    return jp[a][0];
}

void superbinsearch()
{
    int leftt = q;
    while (leftt > 0)
    {
        for(int i = 0; i < m; i++)
        {
            upd(preorder[vfe[adds[i].second]], adds[i].first, 1);
            upd(postorder[vfe[adds[i].second]], -adds[i].first, -1);

            for(int qnum : mids[i])
            {
                long long wyn = 0;
                int a = queries[qnum].a;
                int b = queries[qnum].b;
                if(checked[a] < checked[b])
                {
                    swap(a, b);
                }
                wyn += treequery(preorder[queries[qnum].lca], preorder[a]);
                wyn -= tree[preorder[queries[qnum].lca] + base].first;
                if(b != queries[qnum].lca)
                {
                    wyn += treequery(preorder[queries[qnum].lca], preorder[b]);
                    wyn -= tree[preorder[queries[qnum].lca] + base].first;
                }
                //cout << "mid" << i << " qnum" << qnum << " wyn" << wyn << endl;

                if(wyn > queries[qnum].silver)
                {
                    queries[qnum].r = queries[qnum].mid - 1;
                }
                else
                {
                    queries[qnum].l = queries[qnum].mid + 1;
                }

                if(queries[qnum].r < queries[qnum].l)
                {
                    leftt--;
                    queries[qnum].wyn = queries[qnum].r;
                }
                else
                {
                    queries[qnum].mid = (queries[qnum].l + queries[qnum].r)/2;
                    mids[queries[qnum].mid].push_back(qnum);
                }
            }
            mids[i].clear();
        }
        for(int i = 0; i < 2*n + base + 1000; i++)
        {
            tree[i].first = 0;
            tree[i].second = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    base = 2 * n;
    for(int i = 1; i <= n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        tab[a].push_back({b, i});
        tab[b].push_back({a, i});
    }
    dfs(1, 1);

    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adds.push_back({b, a});
    }


    for(int i = 0; i < q; i++)
    {
        int a, b, c;
        long long d;
        cin >> a >> b >> c >> d;
        query que;
        que.a = a;
        que.b = b;
        que.gold = c;
        que.silver = d;
        que.l = 0;
        que.r = m-1;
        que.mid = (m-1)/2;
        que.lca = LCA(a, b);
        mids[que.mid].push_back(i);
        queries.push_back(que);
    }
    sort(adds.begin(), adds.end());
    superbinsearch();

    for(int i = 0; i < q; i++)
    {
        mids[queries[i].wyn].push_back(i);
    }

    for(int i = 0; i < m; i++)
    {
        upd(preorder[vfe[adds[i].second]], adds[i].first, 1);
        upd(postorder[vfe[adds[i].second]], -adds[i].first, -1);

        for(int qnum : mids[i])
        {
            int wyn = 0;
            int a = queries[qnum].a;
            int b = queries[qnum].b;
            if(checked[a] < checked[b])
            {
                swap(a, b);
            }
            wyn += treequeryamount(preorder[queries[qnum].lca], preorder[a]);
            wyn -= tree[preorder[queries[qnum].lca] + base].second;
            if(b != queries[qnum].lca)
            {
                wyn += treequeryamount(preorder[queries[qnum].lca], preorder[b]);
                wyn -= tree[preorder[queries[qnum].lca] + base].second;
            }
            queries[qnum].coinsatloss = wyn;
        }
        mids[i].clear();
    }

    for(int i = 0; i < q; i++)
    {
        int wyn = 0;
        int a = queries[i].a;
        int b = queries[i].b;
        if(checked[a] < checked[b])
        {
            swap(a, b);
        }
        wyn += treequeryamount(preorder[queries[i].lca], preorder[a]);
        wyn -= tree[preorder[queries[i].lca] + base].second;
        if(b != queries[i].lca)
        {
            wyn += treequeryamount(preorder[queries[i].lca], preorder[b]);
            wyn -= tree[preorder[queries[i].lca] + base].second;
        }
       // cout << "wyn " << wyn << " buyable " << queries[i].coinsatloss << endl;
        
        cout << max(-1, queries[i].gold - wyn + queries[i].coinsatloss) << endl;
    }

}

Compilation message (stderr)

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

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