제출 #1143634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143634		Der_Vlapos	Two Currencies (JOI23_currencies)	C++20	100 / 100	1348 ms	55060 KiB

currencies

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

#define int ll

struct segTreeSum
{
    vector<ll> tree;
    int sz;

    void init(int n)
    {
        sz = n;
        tree.resize(2 * sz);
    }

    void build(vector<int> &a)
    {
        init(a.size());
        for (int i = 0; i < a.size(); ++i)
            tree[i + sz] = a[sz];

        for (int i = sz - 1; i > 0; --i)
            tree[i] = tree[i << 1] + tree[(i << 1) + 1];
    }

    int get(int l, int r) // [l, r)
    {
        l += sz;
        r += sz;
        int res = 0;

        while (l < r)
        {
            if (l & 1)
                res += tree[l++];
            if (r & 1)
                res += tree[--r];
            l >>= 1;
            r >>= 1;
        }

        return res;
    }

    void add(int pos, int val)
    {
        pos += sz;
        tree[pos] += val;
        pos >>= 1;
        while (pos)
        {
            tree[pos] = tree[pos << 1] + tree[(pos << 1) + 1];
            pos >>= 1;
        }
    }
};

struct test
{
    vector<vector<pii>> tree;
    vector<vector<int>> jump;
    vector<int> tin, tout, edgeV, ans;
    int timer = 0;
    segTreeSum ecnt, esum;

    void dfs(int v, int pr = -1)
    {
        tin[v] = timer++;
        for (auto [tov, id] : tree[v])
            if (tov != pr)
            {
                jump[tov][0] = v;

                for (int k = 1; k < 20; ++k)
                    jump[tov][k] = jump[jump[tov][k - 1]][k - 1];

                edgeV[id] = tov;
                dfs(tov, v);
            }
        tout[v] = timer++;
    }

    bool isP(int pr, int v)
    {
        return tin[pr] <= tin[v] and tout[v] <= tout[pr];
    }

    int lca(int v, int u)
    {
        if (isP(v, u))
            return v;
        if (isP(u, v))
            return u;
        for (int k = 19; k >= 0; --k)
            if (!isP(jump[v][k], u))
                v = jump[v][k];
        return jump[v][0];
    }

    void solve(vector<pair<pii, pii>> &qrs, vector<pii> &els, int &u, int L, int R)
    {
        int M = (L + R) >> 1;

        // move u to M
        {
            while (u < M)
            {
                int v = edgeV[els[u].s];

                ecnt.add(tin[v], 1);
                ecnt.add(tout[v], -1);
                esum.add(tin[v], els[u].f);
                esum.add(tout[v], -els[u].f);

                u++;
            }
            while (u > M)
            {
                u--;

                int v = edgeV[els[u].s];

                ecnt.add(tin[v], -1);
                ecnt.add(tout[v], 1);
                esum.add(tin[v], -els[u].f);
                esum.add(tout[v], els[u].f);
            }
        }

        vector<pair<pii, pii>> win, lose;
        for (auto [bf1, bf2] : qrs)
        {
            auto [id, c] = bf1;
            auto [v, u] = bf2;

            int sum = esum.get(0, tin[v] + 1) + esum.get(0, tin[u] + 1) - 2 * esum.get(0, tin[lca(v, u)] + 1);
            if (sum <= c)
            {
                win.pb({bf1, bf2});
                ans[id] = ecnt.get(0, tin[v] + 1) + ecnt.get(0, tin[u] + 1) - 2 * ecnt.get(0, tin[lca(v, u)] + 1);
            }
            else
            {
                lose.pb({bf1, bf2});
            }
        }
        qrs.clear();
        qrs.shrink_to_fit();

        if (R - L > 1)
        {
            solve(lose, els, u, L, M);
            solve(win, els, u, M, R);
        }
        else
            assert(lose.size() == 0);
    }

    void solve(int testcase)
    {
        boost();

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

        ecnt.init(n * 2);
        esum.init(n * 2);
        ans.resize(q);
        tree.resize(n);
        tin.resize(n);
        tout.resize(n);
        jump.resize(n, vector<int>(20));
        edgeV.resize(n - 1, 0);

        for (int i = 0; i < n - 1; ++i)
        {
            int x, y;
            cin >> x >> y;
            --x, --y;
            tree[x].pb({y, i});
            tree[y].pb({x, i});
        }
        dfs(0);
        vector<pii> els;
        for (int i = 0; i < m; ++i)
        {
            int p, c;
            cin >> p >> c;
            --p;
            els.pb({c, p});
        }

        sort(all(els));
        vector<int> S(q), T(q), X(q), Y(q);
        vector<pair<pii, pii>> qrs;
        for (int i = 0; i < q; ++i)
        {
            cin >> S[i] >> T[i] >> X[i] >> Y[i];
            --S[i];
            --T[i];
            qrs.pb({{i, Y[i]}, {S[i], T[i]}});
        }
        int u = 0;
        solve(qrs, els, u, 0, els.size() + 1);

        assert(u == els.size());

        for (int i = 0; i < q; ++i)
        {
            int v = S[i];
            int u = T[i];
            int cntNeeded = ecnt.get(0, tin[v] + 1) + ecnt.get(0, tin[u] + 1) - 2 * ecnt.get(0, tin[lca(v, u)] + 1) - ans[i];
            cout << max(X[i] - cntNeeded, (ll)-1) << "\n";
        }
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                                Coded by Der_Vlapos                                 //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp:308:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  308 | main()
      | ^~~~

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