Submission #564366

#	Time	Username	Problem	Language	Result	Execution time	Memory
564366		KoD	Tug of War (BOI15_tug)	C++17	100 / 100	63 ms	8372 KiB

tug

#include <bits/stdc++.h>

using std::pair;
using std::vector;

constexpr int MAX_S = 20;
constexpr int MAX_N = 30000;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K;
    std::cin >> N >> K;
    const int V = 2 * N;
    vector<int> L(V), R(V), S(V);
    vector<vector<pair<int, int>>> graph(V);
    for (int i = 0; i < V; ++i) {
        std::cin >> L[i] >> R[i] >> S[i];
        L[i] -= 1;
        R[i] -= 1;
        R[i] += N;
        graph[L[i]].emplace_back(R[i], i);
        graph[R[i]].emplace_back(L[i], i);
    }
    vector<int> deg(V);
    std::queue<int> que;
    for (int i = 0; i < V; ++i) {
        deg[i] = graph[i].size();
        if (deg[i] <= 1) {
            que.push(i);
        }
    }
    int fixed = 0;
    vector<char> done(V);
    while (!que.empty()) {
        const int u = que.front();
        que.pop();
        bool found = false;
        for (const auto& [v, e] : graph[u]) {
            if (!done[v]) {
                deg[v] -= 1;
                if (deg[v] == 1) {
                    que.push(v);
                }
                fixed += u < N ? S[e] : -S[e];
                found = true;
                break;
            }
        }
        if (!found) {
            std::cout << "NO\n";
            return 0;
        }
        done[u] = true;
    }
    const int W = MAX_S * N + 1;
    vector<int> count(W);
    for (int i = 0; i < V; ++i) {
        if (done[i]) {
            continue;
        }
        int u = i, p = -1, sum = 0;
        vector<int> cycle;
        while (true) {
            cycle.push_back(u);
            for (const auto& [v, e] : graph[u]) {
                if (!done[v] and e != p) {
                    sum += u < N ? S[e] : -S[e];
                    p = e;
                    u = v;
                    break;
                }
            }
            if (u == i) {
                break;
            }
        }
        for (const int u : cycle) {
            done[u] = true;
        }
        if (sum < 0) {
            sum = -sum;
        }
        fixed -= sum;
        count[sum] += 1;
    }
    std::bitset<MAX_S * MAX_N + 1> dp;
    dp.set(0);
    for (int i = 0; i < W; ++i) {
        if (count[i] == 0) {
            continue;
        }
        if (count[i] >= 3) {
            const int t = (count[i] - 1) / 2;
            count[i] -= 2 * t;
            count[2 * i] += t;
        }
        while (count[i]--) {
            dp |= dp << i;
        }
    }
    for (int i = 0; i < W; ++i) {
        if (std::abs(fixed + 2 * i) <= K and dp.test(i)) {
            std::cout << "YES\n";
            return 0;
        }
    }
    std::cout << "NO\n";
    return 0;
}

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