Submission #1185858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185858		Rokas159	Tug of War (BOI15_tug)	C++20	23 / 100	316 ms	3652 KiB

tug

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

#define int long long

#define NO {cout << "NO" << endl; cout.flush(); return 0;}
#define YES {cout << "YES" << endl; cout.flush(); return 0;}

const int MAXN = 3e4+2;

typedef bitset<20*MAXN> bt;

vector<pair<int,int>> adj[MAXN*2];
int laipsnis[MAXN*2];

int n, k;

int side(int i) {
    if (i < n) return 0;
    return 1;
}

signed main() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    // freopen("tug_wrong.in", "r", stdin);

    cin >> n >> k;

    bool exists[n*2];

    int totalPower = 0;

    for (int i = 0; i < 2*n; i++) {
        int l, r, s;
        cin >> l >> r >> s;

        totalPower += s;

        // cerr << l-1 << " " << r+n-1 << " " << s << endl;

        adj[l-1].push_back({n+r-1,s});
        adj[n+r-1].push_back({l-1,s});
        laipsnis[n+r-1]++;
        laipsnis[l-1]++;
        exists[i] = true;
    }

    int sum[2] = {0,0};

    for (int i = 0; i < 2*n; i++) {
        if (exists[i] && laipsnis[i] == 0) {
            NO;
        }

        if (exists[i] && laipsnis[i] == 1) {
            queue<int> q;
            q.push(i);

            while (!q.empty()) {
                int s = q.front();
                q.pop();

                exists[s] = false;

                for (auto [u, w] : adj[s]) {
                    laipsnis[u]--;

                    if (exists[u]) {
                        sum[side(s)] += w;
                    }

                    if (exists[u] && laipsnis[u] == 1) {
                        
                        q.push(u);
                    }
                }
            }
        }
    }

    bt dp;
    dp[0] = 1;

    bt a = dp << sum[0];
    bt b = dp << sum[1];

    // cerr << "---------------" << endl;

    // cerr << sum[0] << " " << sum[1] << endl;

    dp |= (a | b);


    for (int i = 0; i < 2*n; i++) { 
        if (exists[i]) {
            if (laipsnis[i] != 2) {
                NO;
            }

            int currSumInd = 0;
            int tempSum[2] = {0,0};

            queue<int> q;
            q.push(i);

            int pirmas_svoris = -1;

            while (!q.empty()) {
                int s = q.front();
                q.pop();
                
                bool cont = false;
                for (auto [u, w] : adj[s]) {
                    if (exists[u] && u != i) {
                        tempSum[currSumInd] += w;
                        currSumInd = (currSumInd+1)%2;

                        pirmas_svoris = w;
                        
                        exists[u] = false;
                        q.push(u);
                        cont = true;
                        break;
                    }
                }

                if (cont) continue;

                bool briauna_panaikinta = false;

                for (auto [u, w] : adj[s]) {
                    if (exists[u]) {
                        if (!briauna_panaikinta && w == pirmas_svoris) {
                            briauna_panaikinta = true;
                            continue;
                        }

                        tempSum[currSumInd] += w;
                        currSumInd = (currSumInd+1)%2;
                        exists[u] = false;
                        
                        q.push(u);
                        break;
                    }
                }
            }

            a = dp << tempSum[0];
            b = dp << tempSum[1];

            // cerr << tempSum[0] << " " << tempSum[1] << endl;

            dp |= (a | b);
        }

        
    }

    for (int i = totalPower/2; totalPower-i-i <= k; i--) {
        // cerr << i << endl;
        if (dp[i]) {
            YES;
        }
    }

    NO;

    return 0;
}

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