Submission #719835

#	Time	Username	Problem	Language	Result	Execution time	Memory
719835		four_specks	Tug of War (BOI15_tug)	C++17	100 / 100	762 ms	5992 KiB

tug

#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>>;

    template <typename T>
    bool ckmin(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }

    template <typename T>
    bool ckmax(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

} // namespace

using BS = bitset<400'001>;

void solve()
{
    int n, k;
    cin >> n >> k;

    vector<int> l(2 * n), r(2 * n), s(2 * n);
    for (int i = 0; i < 2 * n; i++)
        cin >> l[i] >> r[i] >> s[i], --l[i], --r[i];

    vector<int> par(2 * n, -1);
    vector<bool> fin(2 * n, 0);

    YCombinator find = [&](auto self, int x) -> int
    { return par[x] < 0 ? x : par[x] = self(par[x]); };

    auto unite = [&](int x, int y) -> bool
    {
        x = find(x);
        y = find(y);

        if (x == y)
        {
            fin[x] = 1;
            return 0;
        }

        if (par[x] > par[y])
            swap(x, y);

        if (fin[y])
            fin[x] = 1;

        par[x] += par[y];
        par[y] = x;

        return 1;
    };

    for (int i = 0; i < 2 * n; i++)
        unite(l[i], r[i] + n);

    bool good = 0;

    bool ok = 1;
    for (int i = 0; i < 2 * n; i++)
        ok &= fin[find(i)];

    if (ok)
    {
        int sum = 0;
        for (int i = 0; i < 2 * n; i++)
            sum += s[i];

        vector<vector<pair<int, int>>> adj(2 * n);
        for (int i = 0; i < 2 * n; i++)
        {
            adj[l[i]].emplace_back(r[i] + n, i);
            adj[r[i] + n].emplace_back(l[i], i);
        }

        vector<bool> done_p(2 * n, 0), done_q(2 * n, 0), used(2 * n, 0), vis(2 * n, 0);

        auto calc = [&](int w) -> array<int, 2>
        {
            int j = -1;
            {
                queue<int> que;

                que.push(w);
                vis[w] = 1;
                while (j == -1)
                {
                    int u = que.front();
                    que.pop();

                    for (auto [v, i] : adj[u])
                    {
                        if (!used[i])
                        {
                            if (vis[v])
                            {
                                j = i;
                                break;
                            }

                            que.push(v);
                            vis[v] = 1;

                            used[i] = 1;
                        }
                    }
                }
            }

            int p = 0, q = 0;
            {
                queue<int> que;
                p += s[j];
                que.push(l[j]);
                done_p[l[j]] = 1;
                while (!que.empty())
                {
                    int u = que.front();
                    que.pop();

                    for (auto [v, i] : adj[u])
                    {
                        if (!done_p[v] && i != j)
                        {
                            if (v < n)
                                p += s[i];

                            que.push(v);
                            done_p[v] = 1;
                        }
                    }
                }
            }
            {
                queue<int> que;
                que.push(r[j] + n);
                done_q[r[j] + n] = 1;
                while (!que.empty())
                {
                    int u = que.front();
                    que.pop();

                    for (auto [v, i] : adj[u])
                    {
                        if (!done_q[v] && i != j)
                        {
                            if (v < n)
                                q += s[i];

                            que.push(v);
                            done_q[v] = 1;
                        }
                    }
                }
            }

            return {p, q};
        };

        BS bs = 1;
        for (int i = 0; i < 2 * n; i++)
        {
            if (!done_p[i])
            {
                auto [p, q] = calc(i);
                bs |= (bs << p) | (bs << q);
            }
        }

        for (int p = (int)bs._Find_first(); p != (int)bs.size(); p = (int)bs._Find_next(p))
            good |= abs(sum - 2 * p) <= k;
    }

    cout << (good ? "YES" : "NO") << '\n';
}

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

    solve();

    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29