Submission #890872

#	Time	Username	Problem	Language	Result	Execution time	Memory
890872		shiomusubi496	Tug of War (BOI15_tug)	C++17	100 / 100	74 ms	4764 KiB

tug

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(v) begin(v), end(v)

struct edge {
    int to, cost;
    edge(int t, int c) : to(t), cost(c) {}
};

int main() {
    int n, k; cin >> n >> k;
    vector<vector<edge>> g(2 * n);
    rep (i, 2 * n) {
        int l, r, s; cin >> l >> r >> s;
        g[--l].emplace_back(--r + n, s);
        g[r + n].emplace_back(l, s);
    }
    vector<bool> used(2 * n, false);
    int sm = 0;
    {
        vector<int> deg(2 * n);
        queue<int> que;
        rep (i, 2 * n) {
            deg[i] = g[i].size();
            if (deg[i] == 1) que.push(i);
            if (deg[i] == 0) {
                puts("NO");
                return 0;
            }
        }
        while (!que.empty()) {
            int v = que.front(); que.pop();
            if (deg[v] != 1) {
                puts("NO");
                return 0;
            }
            used[v] = true;
            for (auto e : g[v]) {
                if (used[e.to]) continue;
                if (v < n) sm += e.cost;
                else sm -= e.cost;
                --deg[e.to];
                if (deg[e.to] == 1) que.push(e.to);
            }
        }
    }
    vector<int> a;
    rep (i, 2 * n) {
        if (used[i]) continue;
        used[i] = true;
        int tmp = 0, sgn = 1;
        int v = -1;
        for (auto e : g[i]) {
            if (!used[e.to]) {
                if (v == -1) {
                    v = e.to;
                    tmp += e.cost;
                }
                else {
                    tmp -= e.cost;
                }
            }
        }
        sgn = -sgn;
        while (v != i) {
            used[v] = true;
            bool flag = true;
            for (auto e : g[v]) {
                if (!used[e.to]) {
                    v = e.to;
                    tmp += e.cost * sgn;
                    sgn = -sgn;
                    flag = false;
                    break;
                }
            }
            if (flag) break;
        }
        tmp = abs(tmp);
        sm -= tmp;
        a.push_back(tmp * 2);
    }
    {
        map<int, int> mp;
        for (auto i : a) ++mp[i];
        vector<int> b;
        while (!mp.empty()) {
            auto [k, v] = *mp.begin(); mp.erase(mp.begin());
            int t = (v - 1) / 2;
            if (t > 0) mp[k * 2] += t;
            v -= t * 2;
            rep (_, v) b.push_back(k);
        }
        a = move(b);
    }
    bitset<1200001> dp(1);
    for (auto x : a) dp |= dp << x;
    bool f = false;
    rep2 (i, max(0, -k - sm), k - sm + 1) {
        if (dp[i]) f = true;
    }
    puts(f ? "YES" : "NO");
}

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