Submission #156016

#	Time	Username	Problem	Language	Result	Execution time	Memory
156016		lyc	Tug of War (BOI15_tug)	C++14	100 / 100	2501 ms	11128 KiB

tug

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

const int MX_N = 30001;
const int MX_S = 21;

int N, K;
int L[2*MX_N], R[2*MX_N], S[2*MX_N];
set<int> al[2*MX_N];
queue<int> q;
bitset<2*MX_N*MX_S> dp;

void die() {
    cout << "NO" << '\n';
    exit(0);
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < 2*N; ++i) {
        cin >> L[i] >> R[i] >> S[i]; R[i] += N;
        al[L[i]].insert(i);
        al[R[i]].insert(i);
    }

    for (int u = 1; u <= 2*N; ++u) {
        if (al[u].empty()) die();
        else if ((int)al[u].size() == 1) q.push(u);
    }

    int mini = 0 + N*20;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (al[u].empty()) die();
        int i = *al[u].begin();
        mini += (u <= N ? S[i] : -S[i]);
        int v = L[i] ^ R[i] ^ u;
        al[u].erase(i);
        al[v].erase(i);
        if ((int)al[v].size() == 1) q.push(v);
    }

    vector<int> flip;
    for (int l = 1; l <= N; ++l) {
        if (al[l].empty()) continue;
        int cyc = 0;
        for (int u = l; !al[u].empty();) {
            int i = *al[u].begin();
            cyc += (u <= N ? S[i] : -S[i]);
            int v = L[i] ^ R[i] ^ u;
            al[u].erase(i);
            al[v].erase(i);
            u = v;
        }
        cyc = abs(cyc);
        mini -= cyc;
        flip.push_back(2*cyc);
    }

    dp[mini] = 1;
    for (int x : flip) dp |= dp << x;
    for (int i = N*20-K; i <= N*20+K; ++i) if (dp[i]) {
        cout << "YES" << '\n';
        return 0;
    }
    die();
}

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