Submission #854754

#	Time	Username	Problem	Language	Result	Execution time	Memory
854754		boris_mihov	Two Currencies (JOI23_currencies)	C++17	100 / 100	1494 ms	269792 KiB

currencies

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 100;
const int INF  = 1e9;

int n, m, q;
struct PersistentSegmentTree
{
    struct Node
    {
        llong sum;
        int active;
        int l, r;

        Node()
        {
            sum = l = r = active = 0;
        }
    };

    int cnt;
    Node tree[MAXN * MAXLOG];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].sum = 0;
            tree[node].active = 0;
            return;
        }

        int mid = (l + r) / 2;
        tree[node].l = cnt++;
        tree[node].r = cnt++;

        build(l, mid, tree[node].l);
        build(mid + 1, r, tree[node].r);
        tree[node].sum = 0;
        tree[node].active = 0;
    }

    void update(int l, int r, int node, int oldNode, int queryPos, int queryVal)
    {
        tree[node].l = tree[oldNode].l;
        tree[node].r = tree[oldNode].r;
        tree[node].sum = tree[oldNode].sum;
        tree[node].active = tree[oldNode].active;

        if (l == r)
        {
            tree[node].sum = queryVal;
            tree[node].active = 1;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid)
        {
            tree[node].l = ++cnt; 
            update(l, mid, tree[node].l, tree[oldNode].l, queryPos, queryVal);
        } else
        {
            tree[node].r = ++cnt; 
            update(mid + 1, r, tree[node].r, tree[oldNode].r, queryPos, queryVal);
        }

        tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
        tree[node].active = tree[tree[node].l].active + tree[tree[node].r].active;
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (node == 0)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR)
        {
            return tree[node].sum;
        }

        llong sum = 0;        
        int mid = (l + r) / 2;
        if (queryL <= mid)
        {
            sum += query(l, mid, tree[node].l, queryL, queryR);
        }

        if (mid + 1 <= queryR)
        {
            sum += query(mid + 1, r, tree[node].r, queryL, queryR);
        }

        return sum;
    }

    int queryActive(int l, int r, int node, int queryL, int queryR)
    {
        if (node == 0)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR)
        {
            return tree[node].active;
        }

        int sum = 0;        
        int mid = (l + r) / 2;
        if (queryL <= mid)
        {
            sum += queryActive(l, mid, tree[node].l, queryL, queryR);
        }

        if (mid + 1 <= queryR)
        {
            sum += queryActive(mid + 1, r, tree[node].r, queryL, queryR);
        }

        return sum;
    }

    void build()
    {
        cnt = 1;
        build(1, m, 1);
    }

    int update(int idx, int pos, int val)
    {
        int root = ++cnt;
        update(1, m, root, idx, pos, val);
        return root;
    }

    llong query(int idx, int l, int r)
    {
        return query(1, m, idx, l, r);
    }

    int queryActive(int idx, int l, int r)
    {
        return queryActive(1, m, idx, l, r);
    }
};

struct SparseLCA
{
    int sparse[MAXLOG][MAXN];
    int dep[MAXN];

    void build(int par[], int d[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = par[i];
            dep[i] = d[i];
        }

        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int i = 1 ; i <= n ; ++i)
            {
                sparse[lg][i] = sparse[lg - 1][sparse[lg - 1][i]];
            }
        }
    }

    int equalize(int u, int v)
    {
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (dep[sparse[log][u]] >= dep[v])
            {
                u = sparse[log][u];
            }
        }

        return u;
    }

    int calcLCA(int u, int v)
    {
        if (u == v)
        {
            return u;
        }

        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (sparse[log][u] != sparse[log][v])
            {
                u = sparse[log][u];
                v = sparse[log][v];
            }
        }

        return sparse[0][u];
    }

    int findLCA(int u, int v)
    {
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        return calcLCA(equalize(u, v), v);
    }
};

SparseLCA sparse;
PersistentSegmentTree tree;
std::vector <int> g[MAXN];
std::vector <int> edgesToAdd[MAXN];
int from[MAXN];
int to[MAXN];
int p[MAXN];
int c[MAXN];
int perm[MAXN];
int inPerm[MAXN];
int idx[MAXN];
int par[MAXN];
int dep[MAXN];

void dfs(int node, int p)
{
    par[node] = p;
    dep[node] = dep[p] + 1;

    for (const int &u : g[node])
    {
        if (u == p)
        {
            continue;
        }

        dfs(u, node);
    }
}

void dfsBuild(int node, int parIdx)
{
    idx[node] = parIdx;
    for (const int &i : edgesToAdd[node])
    {
        idx[node] = tree.update(idx[node], inPerm[i], c[i]);
    }

    for (const int &u : g[node])
    {
        if (u == par[node])
        {
            continue;
        }

        dfsBuild(u, idx[node]);
    }
}

void solve()
{
    dfs(1, 0);
    sparse.build(par, dep);
    tree.build();

    std::iota(perm + 1, perm + 1 + m, 1);
    std::sort(perm + 1, perm + 1 + m, [&](int x, int y)
    {
        return c[x] < c[y];
    });

    for (int i = 1 ; i <= m ; ++i)
    {
        inPerm[perm[i]] = i;
    }

    for (int i = 1 ; i < n ; ++i)
    {
        if (from[i] == par[to[i]])
        {
            std::swap(from[i], to[i]);
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        edgesToAdd[from[p[i]]].push_back(i);
    }

    dfsBuild(1, 1);
    for (int i = 1 ; i <= q ; ++i)
    {
        int x, y, gold, lca;
        llong silver;

        std::cin >> x >> y >> gold >> silver;
        lca = sparse.findLCA(x, y);

        int l = 0, r = m + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree.query(idx[x], 1, mid) + tree.query(idx[y], 1, mid) - 2 * tree.query(idx[lca], 1, mid) <= silver) l = mid;
            else r = mid;
        } 

        if (r == m + 1)
        {
            std::cout << gold << '\n';
        } else
        {
            int curr = tree.queryActive(idx[x], r, m) + tree.queryActive(idx[y], r, m) - 2 * tree.queryActive(idx[lca], r, m);
            if (gold < curr) std::cout << -1 << '\n';
            else std::cout << gold - curr << '\n';
        }
    }
}  

void input()
{
    std::cin >> n >> m >> q;
    for (int i = 1 ; i < n ; ++i)
    {
        std::cin >> from[i] >> to[i];
        g[from[i]].push_back(to[i]);
        g[to[i]].push_back(from[i]);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> p[i] >> c[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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