Submission #1306817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306817		mikolaj00	Two Currencies (JOI23_currencies)	C++20	100 / 100	3090 ms	38848 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int ceil_lg(int k)
{
    int res = __lg(k);
    if (1<<res < k)
        res++;
    return res;
}

struct SegTree
{
    SegTree(int size)
    {
        int k = 1<<(ceil_lg(size)+1);
        arr.resize(k);
        lazy.resize(k);
    }

    void push(int v)
    {
        arr[v<<1] += lazy[v];
        lazy[v<<1] += lazy[v];
        arr[(v<<1)+1] += lazy[v];
        lazy[(v<<1)+1] += lazy[v];
        lazy[v] = 0;
    }

    void update(int l, int r, ll val, int v = 1, int a = 0, int b = -1)
    {
        if (b == -1)
            b = (arr.size()>>1)-1;

        if (b < l || a > r)
            return;
        else if (a >= l && b <= r)
        {
            lazy[v] += val;
            arr[v] += val;
        }
        else
        {
            int mid = (a+b)>>1;
            push(v);
            update(l, r, val, v<<1, a, mid);
            update(l, r, val, (v<<1)+1, mid+1, b);
        }
    }

    ll query(int k, int v = 1, int a = 0, int b = -1)
    {
        if (b == -1)
            b = (arr.size()>>1)-1;

        if (b < k || a > k)
            return 0;
        else if (a == k && b == k)
            return arr[v];
        else
        {
            int mid = (a+b)>>1;
            push(v);
            return query(k, v<<1, a, mid) + query(k, (v<<1)+1, mid+1, b);
        }
    }

    vector<ll> arr;
    vector<ll> lazy;
};

vector<vector<int>> g;
vector<int> pre, post;
vector<int> dep;
vector<vector<int>> up;
vector<pair<int, int>> edges;

struct Checkpoint
{
    int v;
    ll c;

    friend bool operator<(Checkpoint const& c1, Checkpoint const& c2)
    {
        return c1.c < c2.c;
    }
};

struct Query
{
    int s, t;
    ll x, y;
    int l, r;
    int idx;

    friend bool operator<(Query const& q1, Query const& q2)
    {
        return (q1.l + q1.r + 1)>>1 < (q2.l + q2.r + 1)>>1;
    }
};

int lca(int a, int b)
{
    if (dep[a] < dep[b])
        swap(a, b);

    for (int i = up[a].size()-1; i >= 0; i--)
    {
        int a_ = up[a][i];
        if (dep[a_] >= dep[b])
            a = a_;
    }

    if (a == b)
        return a;

    for (int i = up[a].size()-1; i >= 0; i--)
    {
        int a_ = up[a][i], b_ = up[b][i];
        if (a_ != b_)
        {
            a = a_;
            b = b_;
        }
    }

    return up[a][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    g.resize(n+1);
    pre.resize(n+1);
    post.resize(n+1);
    dep.resize(n+1);
    up.resize(n+1, vector<int>(__lg(n)+1));
    edges.resize(n-1);

    for (int i = 0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;

        edges[i] = {a, b};

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dep[0] = -1;
    int time = 0;
    function<void(int, int)> dfs = [&](int u, int p) -> void
    {
        pre[u] = time++;
        dep[u] = dep[p] + 1;

        up[u][0] = p;
        for (int i = 1; i < up[u].size(); i++)
            up[u][i] = up[up[u][i-1]][i-1];

        for (auto v : g[u])
            if (v != p)
                dfs(v, u);

        post[u] = time;
    };
    dfs(1, 0);

    vector<Checkpoint> checkpoints(m);
    for (int i = 0; i < m; i++)
    {
        int p, c;
        cin >> p >> c;

        auto[a, b] = edges[p-1];

        if (pre[a] < pre[b])
            checkpoints[i] = {b, c};
        else
            checkpoints[i] = {a, c};
    }

    sort(checkpoints.begin(), checkpoints.end());
    
    vector<Query> queries(q);
    for (int i = 0; i < q; i++)
    {
        cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
        queries[i].l = 0;
        queries[i].r = m;
        queries[i].idx = i;
    }

    while (true)
    {
        vector<Query*> cur_queries;
        for (auto& q : queries)
            if (q.l != q.r)
                cur_queries.push_back(&q);

        if (cur_queries.empty())
            break;

        // cout << cur_queries[0]->l << ' ' << cur_queries[0]->r << '\n';

        sort(cur_queries.begin(), cur_queries.end(), [](Query* q1, Query* q2) -> bool {return *q1 < *q2;});
        int p = 0;

        SegTree st(n);

        for (int i = 0; i <= m; i++)
        {
            for (; p < cur_queries.size(); p++)
            {
                Query& q = *cur_queries[p];
                int mid = (q.l + q.r + 1)>>1;
                if (mid > i)
                    break;

                int l = lca(q.s, q.t);
                ll val = st.query(pre[q.s]) + st.query(pre[q.t]) - (st.query(pre[l])<<1);

                if (val <= q.y)
                    q.l = mid;
                else
                    q.r = mid-1;
            }

            if (i < m)
            {
                Checkpoint c = checkpoints[i];
                st.update(pre[c.v], post[c.v]-1, c.c);
            }

            // for (int i = 0; i < n; i++)
            //     cout << st.query(i) << ' ';
            // cout << '\n';
        }
    }

    SegTree st(n);

    vector<int> ans(q);
    sort(queries.rbegin(), queries.rend());
    int p = 0;
    for (int i = m; i >= 0; i--)
    {
        if (i < m)
        {
            Checkpoint c = checkpoints[i];
            st.update(pre[c.v], post[c.v]-1, 1);
        }

        for (; p < queries.size(); p++)
        {
            Query q = queries[p];
            if (q.l < i)
                break;

            int l = lca(q.s, q.t);
            ans[q.idx] = q.x - (st.query(pre[q.s]) + st.query(pre[q.t]) - (st.query(pre[l])<<1));            
        }
    }

    for (int i = 0; i < q; i++)
        cout << (ans[i] >= 0 ? ans[i] : -1) << '\n';
}

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