Submission #1350957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350957		msab3f	Tug of War (BOI15_tug)	C++20	100 / 100	524 ms	11088 KiB

tug

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 30'000 + 10;
const int MAX_S = 20 + 10;

int n, k, sarr[2 * MAX_N], deg[2 * MAX_N], sum, cnt[MAX_N * MAX_S];
vector<pair<int, int>> adj[2 * MAX_N];
set<pair<int, int>> st;
bool rm[2 * MAX_N], mark[2 * MAX_N];
bitset<MAX_N * MAX_S> bs;

inline void add_edge(int u, int v, int i) {
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
}

int dfs(int u, int e) {
    mark[u] = true;
    for (auto [v, i] : adj[u]) {
        if (rm[v] || i == e) continue;
        if (mark[v]) return sarr[i];
        return sarr[i] - dfs(v, i);
    }
}

int main() {
    cin >> n >> k;

    for (int i = 0; i < 2 * n; ++i) {
        int l, r;
        cin >> l >> r >> sarr[i];
        add_edge(l - 1, r + n - 1, i);
    }

    for (int u = 0; u < 2 * n; ++u) {
        deg[u] = adj[u].size();
        st.insert({deg[u], u});
    }

    while (!st.empty() && st.begin()->first <= 1) {
        int u = st.begin()->second;
        st.erase(st.begin());
        if (deg[u] == 0) {
            cout << "NO\n";
            exit(0);
        }
        rm[u] = true;
        int v, s;
        for (auto [cv, i] : adj[u])
            if (!rm[cv]) {
                v = cv;
                s = sarr[i];
            }
        st.erase({deg[v], v});
        --deg[v];
        st.insert({deg[v], v});
        sum += u < n ? s : -s;
    }

    sum = abs(sum);
    ++cnt[sum];

    for (int u = 0; u < 2 * n; ++u)
        if (!rm[u] && !mark[u]) {
            int diff = abs(dfs(u, -1));
            sum += diff;
            ++cnt[diff];
        }

    bs[0] = true;

    for (int i = 1; i < MAX_N * MAX_S; ++i) {
        // while (cnt[i] >= 3) {
        //     cnt[i] -= 2;
        //     ++cnt[i + 1];
        // }
        while (cnt[i]--) {
            bs |= bs << i;
        }
    }

    for (int i = 0; i < MAX_N * MAX_S; ++i)
        if (bs[i] && abs(2 * i - sum) <= k) {
            cout << "YES\n";
            exit(0);
        }

    cout << "NO\n";
}

Compilation message (stderr)

tug.cpp: In function 'int dfs(int, int)':
tug.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^

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