Submission #735223

#	Time	Username	Problem	Language	Result	Execution time	Memory
735223		four_specks	Two Currencies (JOI23_currencies)	C++17	100 / 100	865 ms	37740 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

struct DSU
{
    DSU(int n) : e(n, -1) {}

    int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); }

    bool same(int u, int v) { return find(u) == find(v); }

    bool unite(int u, int v)
    {
        u = find(u);
        v = find(v);

        if (u == v)
            return 0;

        if (e[u] > e[v])
            swap(u, v);

        e[u] += e[v];
        e[v] = u;

        return 1;
    }

    vector<int> e;
};

template <typename T>
struct Fenwick
{
    Fenwick(int _n) : n(_n), tree(n + 1) {}

    T sum(int p)
    {
        T ret = 0;
        for (; p; p -= p & -p)
            ret += tree[p];
        return ret;
    }

    void add(int p, T x)
    {
        for (p++; p <= n; p += p & -p)
            tree[p] += x;
    }

    int n;
    vector<T> tree;
};

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v, --u, --v;

        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    vector<pair<long, int>> a(m);
    for (auto &[x, j] : a)
        cin >> j >> x, --j;
    sort(a.begin(), a.end());

    vector<int> s(q), t(q);
    vector<long> gold(q), silver(q);
    for (int i = 0; i < q; i++)
        cin >> s[i] >> t[i] >> gold[i] >> silver[i], --s[i], --t[i];

    vector<int> to(n - 1), tin(n), tout(n), pref(n);

    int timer = 0;
    YCombinator(
        [&](auto self, int u, int p) -> void
        {
            tin[u] = timer++;
            for (auto [v, j] : adj[u])
            {
                if (v != p)
                {
                    to[j] = v;
                    self(v, u);
                }
            }
            tout[u] = timer;
        })(0, -1);

    for (auto [x, j] : a)
        pref[to[j]]++;

    YCombinator(
        [&](auto self, int u, int p) -> void
        {
            if (p != -1)
                pref[u] += pref[p];

            for (auto [v, j] : adj[u])
            {
                if (v != p)
                    self(v, u);
            }
        })(0, -1);

    for (int i = 0; i < q; i++)
    {
        if (tin[s[i]] > tin[t[i]])
            swap(s[i], t[i]);
    }

    vector<int> lca(q), cnt(q);

    {
        vector<int> anc(n);
        DSU dsu(n);
        vector<vector<int>> todo(n);

        for (int i = 0; i < q; i++)
            todo[t[i]].push_back(i);

        YCombinator(
            [&](auto self, int u, int p) -> void
            {
                anc[u] = u;
                for (auto [v, j] : adj[u])
                {
                    if (v != p)
                    {
                        self(v, u);
                        dsu.unite(u, v);
                        anc[dsu.find(u)] = u;
                    }
                }

                for (int j : todo[u])
                    lca[j] = anc[dsu.find(s[j])];
            })(0, -1);
    }

    for (int i = 0; i < q; i++)
        cnt[i] = pref[s[i]] + pref[t[i]] - 2 * pref[lca[i]];

    vector res = cnt;

    vector<int> lo(q, 0), hi(q, m);

    while (1)
    {
        vector<vector<int>> met(m);

        bool flag = 0;
        for (int i = 0; i < q; i++)
        {
            if (lo[i] < hi[i])
            {
                met[(lo[i] + hi[i] - 1) / 2].push_back(i);
                flag = 1;
            }
        }

        if (!flag)
            break;

        Fenwick<long> fenw_cost(n);
        Fenwick<int> fenw_cnt(n);

        auto path_cost = [&](int k) -> long
        { return fenw_cost.sum(tin[s[k]] + 1) + fenw_cost.sum(tin[t[k]] + 1) - 2 * fenw_cost.sum(tin[lca[k]] + 1); };

        auto path_cnt = [&](int k) -> int
        { return fenw_cnt.sum(tin[s[k]] + 1) + fenw_cnt.sum(tin[t[k]] + 1) - 2 * fenw_cnt.sum(tin[lca[k]] + 1); };

        for (int i = 0; i < m; i++)
        {
            auto [x, j] = a[i];

            fenw_cost.add(tin[to[j]], x);
            fenw_cost.add(tout[to[j]], -x);

            fenw_cnt.add(tin[to[j]], 1);
            fenw_cnt.add(tout[to[j]], -1);

            for (int k : met[i])
            {
                if (path_cost(k) > silver[k])
                    hi[k] = i;
                else
                {
                    res[k] = cnt[k] - path_cnt(k);
                    lo[k] = i + 1;
                }
            }
        }
    }

    for (int i = 0; i < q; i++)
        cout << max(gold[i] - res[i], -1l) << '\n';
}

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

    solve();

    return 0;
}

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