Submission #1166970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166970		belgianbot	Tug of War (BOI15_tug)	C++20	100 / 100	908 ms	8488 KiB

tug

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

#define int long long

struct a {
    int l, r, s;
};
const int N = 2 * 300000;
int n, k, diff;
vector<set<int>> memo;
vector<int> sum;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    vector<a> b(2*n);
    vector<vector<vector<int>>> pos(2, vector<vector<int>>(n));
    vector<vector<int>> posLeft(2, vector<int>(n));
    vector<int> left(2*n, 2);

    for (int i = 0; i < 2*n; i++) {
        cin >> b[i].l >> b[i].r >> b[i].s;
        b[i].l--, b[i].r--;
        pos[0][b[i].l].push_back(i);
        pos[1][b[i].r].push_back(i);
    }

    queue<pair<int,int>> q;
    diff = 0;
    for (int i = 0; i < n; i++) {
        posLeft[0][i] = pos[0][i].size();
        posLeft[1][i] = pos[1][i].size();
        if (pos[0][i].size() == 1) q.push({0, i});
        if (pos[1][i].size() == 1) q.push({1,i});
        if (pos[0][i].empty() || pos[1][i].empty()) {
            cout << "NO\n";
            return 0;
        }
    }

    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();

        int x = -1;
        for (auto y : pos[i][j]) {
            if (left[y]) x = y;
        }
        if (x == -1) {
            cout << "NO\n";
            return 0;
        }
        if (i) diff -= b[x].s;
        else diff += b[x].s;

        
        left[x] = 0;

        if (i) {
            if (--posLeft[0][b[x].l] == 1) q.push({0, b[x].l});
        }
        else {
            if (--posLeft[1][b[x].r] == 1) q.push({1, b[x].r});
        }
    }

    for (int i = 0; i < 2*n; i++) {
        if (left[i] > 0) {
            int res = 0;
            q.push({0, i});
            while(!q.empty()) {
                auto [i, j] = q.front(); q.pop();
                
                if (left[j] <= 0) continue;
                int curr;
                if (i) {
                    res -= b[j].s;
                    curr = b[j].r;
                }
                else {
                    res += b[j].s;
                    curr = b[j].l;
                }
                left[j] = 0;
                for(int x : pos[i][curr]) {
                    left[x]--;
                    if (left[x] == 1) {
                        if (i) q.push({0, x});
                        else q.push({1, x});
                    }
                }
                if (i) {
                    if (--posLeft[0][b[j].l] == 1) {
                        for (auto y : pos[0][b[j].l]) {
                             if (left[y] > 0) q.push({0, y});
                        } 
                    }
                }   
                else {
                    if (--posLeft[1][b[j].r] == 1) {
                        for (auto y : pos[1][b[j].r]) {
                             if (left[y] > 0) q.push({1, y});
                        } 
                    }
                }
            }
            sum.push_back(abs(res));
        }
    }

    //for (int x : sum) cout << x << ' ';

    memo.resize(sum.size());
    bitset<N> mask; 
    mask[0] = 1; mask = (mask << ((N>>1) + diff));
    for (int i = 0; i < sum.size(); i++) mask = (mask << sum[i]) | (mask >> sum[i]);

    for (int i = (N >> 1) + k; i >= (N >> 1) - k; i--) {
        if (mask[i]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}
       

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