Submission #1251780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251780		NHristov	Two Currencies (JOI23_currencies)	C++20	100 / 100	871 ms	63956 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int LG = 18;

int n, m, queries;

pair < int, int > checks[N];

int s[N], t[N], x[N], y[N];
int lca[N];

vector < pair < int, int > > g[N];
pair < int, int > edges[N];

int dep[N];
int up[LG][N];
int tim = 0;
int tin[N], tout[N];

void dfsBuild(int u, int p)
{
    tin[u] = ++tim;

    for (auto [v, id] : g[u])
    {
        if (v == p)
        {
            continue;
        }

        dep[v] = dep[u] + 1;
        up[0][v] = u;

        for (int i = 1; i < LG; i++)
        {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }

        dfsBuild(v, u);
    }

    tout[u] = ++tim;
}

int calcLCA(int u, int v)
{
    if (dep[u] < dep[v])
    {
        swap(u, v);
    }

    int diff = dep[u] - dep[v];

    for (int i = 0; i < LG; i++)
    {
        if ((diff & (1 << i)))
        {
            u = up[i][u];
            diff -= (1 << i);
        }
    }

    if (u == v)
    {
        return u;
    }

    for (int i = LG - 1; i >= 0; i--)
    {
        if (up[i][u] != up[i][v])
        {
            u = up[i][u];
            v = up[i][v];
        }
    }

    return up[0][u];
}

struct Fenwick
{
    int bit[2 * N];

    void update(int idx, int val)
    {
        while (idx <= 2 * n)
        {
            bit[idx] += val;
            idx += idx & (-idx);
        }
    }

    int query(int idx)
    {
        int sum = 0;

        while (idx >= 1)
        {
            sum += bit[idx];
            idx -= idx & (-idx);
        }

        return sum;
    }

    void clearFenwick()
    {
        for (int i = 1; i <= 2 * n; i++)
        {
            bit[i] = 0;
        }
    }
};

Fenwick silverPath, goldPath;

void updatePath(bool type, int idx, int sign)
{
    int u = checks[idx].second;
    int silverCoins = checks[idx].first;

    if (!type)
    {
        silverPath.update(tin[u], silverCoins * sign);
        silverPath.update(tout[u], -silverCoins * sign);
    }
    else
    {
        goldPath.update(tin[u], sign);
        goldPath.update(tout[u], -sign);
    }
}

int queryPath(bool type, int queryIdx)
{
    int st = s[queryIdx];
    int fi = t[queryIdx];

    if (!type)
    {
        return silverPath.query(tin[st]) + silverPath.query(tin[fi]) - 2 * silverPath.query(tin[lca[queryIdx]]);
    }

    return goldPath.query(tin[st]) + goldPath.query(tin[fi]) - 2 * goldPath.query(tin[lca[queryIdx]]);
}

int L[N], R[N];
int ans[N];

vector < int > v[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> queries;

    for (int i = 1; i < n; i++)
    {
        cin >> edges[i].first >> edges[i].second;

        g[edges[i].first].push_back({edges[i].second, i});
        g[edges[i].second].push_back({edges[i].first, i});
    }

    dfsBuild(1, 0);

    for (int i = 1; i <= m; i++)
    {
        int p, c;

        cin >> p >> c;

        if (tin[edges[p].first] < tin[edges[p].second])
        {
            checks[i] = {c, edges[p].second};
        }
        else
        {
            checks[i] = {c, edges[p].first};
        }
    }

    sort(checks + 1, checks + m + 1);

    for (int i = 1; i <= queries; i++)
    {
        cin >> s[i] >> t[i] >> x[i] >> y[i];

        lca[i] = calcLCA(s[i], t[i]);
    }

    for (int i = 1; i <= queries; i++)
    {
        L[i] = -1, R[i] = m + 1;
        ans[i] = -1;
    }

    for (int i = 1; i <= LG; i++)
    {
        bool stop = 1;

        for (int i = 0; i <= m; i++)
        {
            v[i].clear();
        }

        for (int i = 1; i <= queries; i++)
        {
            if (L[i] <= R[i])
            {
                v[(L[i] + R[i]) / 2].push_back(i);
                stop = 0;
            }
        }

        if (stop)
        {
            break;
        }

        goldPath.clearFenwick();
        silverPath.clearFenwick();

        for (int i = 1; i <= m; i++)
        {
            updatePath(1, i, +1);
        }

        for (int mid = 0; mid <= m; mid++)
        {
            if (mid)
            {
                updatePath(1, mid, -1);
                updatePath(0, mid, +1);
            }

            for (int id : v[mid])
            {
                int currSilver = queryPath(0, id);
                int currGold = queryPath(1, id);

                if (currSilver <= y[id] && currGold <= x[id])
                {
                    ans[id] = x[id] - currGold;
                    L[id] = mid;
                }
                else
                {
                    if (currGold > x[id])
                    {
                        L[id] = mid;
                    }
                    else
                    {
                        R[id] = mid;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= queries; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

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