Submission #1166451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166451		belgianbot	Tug of War (BOI15_tug)	C++20	41 / 100	2743 ms	323872 KiB

tug

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

#define int long long

struct a {
    int l, r, s;
};
int n, k, diff;
vector<set<int>> memo;
vector<int> sum, pref;
bool dp(int i, int curr) {
    
    if (i == (int)(sum.size())) return abs(diff + curr) <= k;
    if (diff+curr+pref[i] < -k && diff+curr - pref[i] > k) return false;
    if (memo[i].find(curr) != memo[i].end()) return false;

    memo[i].insert(curr);
    if (dp(i+1, curr + sum[i]) || dp(i+1, curr - sum[i])) return true;
    else return false;
}

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()); pref.resize(sum.size());
    sort(sum.rbegin(), sum.rend());
    int sm = 0;
    for (int i = 0; i< sum.size(); i++) {
        pref[i] = sm + sum[i];
        sm += sum[i];
    }
    if (dp(0, 0)) cout << "YES\n";
    else cout << "NO\n";
}
       

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