Submission #1000816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000816		LOLOLO	Tug of War (BOI15_tug)	C++17	18 / 100	48 ms	4280 KiB

tug

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e4 + 100;
set <pair <int, int>> ed[N];
bool used[N];
int st = 0;
pair <int, int> dfs(int u, int v) {
    used[u] = 1;
    if (u == st && v)
        return {0, 0};

    pair <int, int> A = {0, 0};
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        A = dfs(x.f, u);
        A.f += x.s;
        swap(A.f, A.s);
    }

    return A;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    int S = 0;
    for (int i = 1; i <= n * 2; i++) {
        int l, r, s;
        cin >> l >> r >> s;
        ed[l].insert({r + n, s});
        ed[r + n].insert({l, s});
        S += s;
    } 

    queue <int> pq;
    int sz = n * 2;
    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) == 0) {
            cout << "NO\n";
            return 0;
        }

        if (sz(ed[i]) == 1)
            pq.push(i);
    }

    int L = 0;
    while (sz(pq)) {
        int t = pq.front();
        pq.pop();
        if (sz(ed[t]) == 0)
            continue;

        auto it = *ed[t].begin();
        int s = it.f, cost = it.s;
        pair <int, int> pat = {t, cost};

        ed[s].erase(pat);
        ed[t].clear();
        if (t <= n)
            L += cost;

        if (sz(ed[s]) == 1) {
            pq.push(s);
        }
    }

    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) > 2) {
            cout << "NO\n";
            return 0;
        }
    }

    bitset <600001> dp;
    dp[0] = 1;

    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) == 2 && used[i] == 0) {
            st = i;
            pair <int, int> A = dfs(i, 0);
            dp = (dp << A.f) | (dp << A.s);
        }
    }


    for (int i = 0; i <= 600000; i++) {
        if (dp[i]) {
            if (abs((S - (L + i)) - (L+ i)) <= k) {
                cout << "YES\n";
                return 0;
            }
        }
    }

    cout << "NO\n";
    return 0;
}


/*
x + s
*/

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