Submission #1111158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111158		Ghulam_Junaid	Tug of War (BOI15_tug)	C++17	100 / 100	475 ms	12884 KiB

tug

#include <bits/stdc++.h>
using namespace std;
 
const int N = 30005;
int n, k, X, Y;
bitset<N * 20> dp;
multiset<pair<int, int>> g[2 * N];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < 2 * n; i ++){
        int l, r, s;
        cin >> l >> r >> s;
        r += n;
        g[l].insert({r, s});
        g[r].insert({l, s});
    }
 
    set<pair<int, int>> st;
    for (int i = 1; i <= 2 * n; i ++)
        st.insert({g[i].size(), i});
 
    while (!st.empty()){
        auto p = *st.begin();
        st.erase(st.begin());
 
        if (p.first > 1) break;
        if (p.first == 0){
            cout << "NO" << endl;
            return 0;
        }
 
        int v = p.second;        
        auto q = *g[v].begin();
        int u = q.first;
        
        if (v <= n)
            X += q.second;
        else
            Y += q.second;
 
        g[v].clear();
        st.erase({g[u].size(), u});
        auto it = g[u].lower_bound({v, q.second});
        g[u].erase(it);
        st.insert({g[u].size(), u});
    }
 
    int cyc = -1;
    int tmp = 1;
    int dif = 0;
    
    int nxt = -1;
    if (!st.empty())
        nxt = (*st.begin()).second;
 
    vector<int> vec;
    while (!st.empty()){
        int v = nxt;
        st.erase({g[v].size(), v});
 
        auto q = *g[v].begin();
        int u = q.first;
        int s = q.second;
 
        nxt = u;
 
        if (cyc == -1){
            cyc = v;
            
            dif += s * tmp;
            tmp *= -1;
            st.erase({g[u].size(), u});
            auto it = g[u].lower_bound({v, s});
            g[u].erase(it);
            st.insert({g[u].size(), u});
        }
        else{
            dif += s * tmp;
            tmp *= -1;
            if (u == cyc){
                vec.push_back(abs(dif));
                cyc = -1;
                dif = 0;
                tmp = 1;
 
                if (!st.empty())
                    nxt = (*st.begin()).second;
            }
            else{
                st.erase({g[u].size(), u});
                g[u].erase({v, s});
                st.insert({g[u].size(), u});
            }
        }
    }
 
    int total = 0;
    for (int x : vec)
        total += x;
 
    if (total >= N * 20){
        cout << "ASDFASF" << endl;
        return 0;
    }
 
    dp[0] = 1;
    for (int x : vec)
        dp |= (dp << x);
 
    for (int sm = 0; sm <= total; sm ++){
        if (dp[sm]){
            if (abs((X + sm) - (total - sm + Y)) <= k){
                cout << "YES" << endl;
                return 0;
            }
        }
    }
 
    cout << "NO" << endl;
    return 0;
}

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