Submission #1111782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111782		Kirill22	Tug of War (BOI15_tug)	C++17	100 / 100	418 ms	15952 KiB

tug

#include "bits/stdc++.h"
 
using namespace std;
 
const int MX = 2 * (int) 1e5;
bitset<MX> dp;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<set<array<int, 3>>> g(2 * n);
    vector<pair<int, int>> e(2 * n);
    vector<int> W(2 * n);
    int L = 0, R = 0;
    for (int i = 0; i < 2 * n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;
        e[i] = {x, y + n};
        W[i] = w;
        g[x].insert({i, y + n, w});
        g[y + n].insert({i, x, w});
    }
    vector<int> deg(2 * n);
    set<pair<int, int>> tmp;
    for (int i = 0; i < 2 * n; i++) {
        deg[i] = (int) g[i].size();
        tmp.insert({deg[i], i});
    }
    while (!tmp.empty()) {
        auto [d, v] = *tmp.begin();
        if (d == 0) {
            cout << "NO\n";
            return;
        }
        tmp.erase(tmp.begin());
        if (d == 1) {
            auto [i, u, w] = *g[v].begin();
            g[v].clear();
            deg[v] = 0;
            (v < n ? L : R) += w;
            tmp.erase({deg[u], u});
            deg[u]--;
            g[u].erase({i, v, w});
            tmp.insert({deg[u], u});
        } else {
            break;
        }
    }
    for (int i = 0; i < 2 * n; i++) {
        assert(deg[i] == 0 || deg[i] == 2);
    }
    dp[MX / 2] = 1;
    vector<int> used(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        if (!used[i] && !g[i].empty()) {
            vector<int> comp = {(*g[i].begin())[0]};
            if (e[comp[0]].first != i) swap(e[comp[0]].first, e[comp[0]].second);
            used[e[comp[0]].second] = 1;
            for (int j = 0; ; j++) {
                bool fnd = false;
                int v = e[comp[j]].second;
                for (auto [id, u, w] : g[v]) {
                    if (id != comp[j] && !used[u]) {
                        fnd = true;
                        comp.push_back(id);
                        used[u] = true;
                        if (e[id].first != v) {
                            swap(e[id].first, e[id].second);
                        }
                        break;
                    }
                }
                if (!fnd) {
                    break;
                }
            }
            int sum = 0;
            for (int i = 0; i < (int) comp.size(); i++) {
                sum += i % 2 == 0 ? W[comp[i]] : -W[comp[i]];
            }
            sum = abs(sum);
//            cout << sum << endl;
            dp = (dp << sum) | (dp >> sum);
        }
    }
//    cout << L << " " << R << endl
    for (int j = 0; j < MX; j++) {
        if (dp[j] && abs(j - MX / 2 + L - R) <= k) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

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