Submission #729814

#	Time	Username	Problem	Language	Result	Execution time	Memory
729814		Tigerpants	Tug of War (BOI15_tug)	C++17	100 / 100	83 ms	11636 KiB

tug

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef set<ll> sll;
typedef vector<sll> vsll;
typedef map<ll, ll> mll_ll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define sz(a) a.size()

const ll MAXW = 20 * 30001;

ll n, k;

vll v;
vpll e;
vsll g;

ll getE(ll i, ll o) {
    return (o == e[i].first) ? e[i].second: e[i].first;
}

vll diffs;

ll DFS(ll cur) {
    if (sz(g[cur]) == 0) {
        return 0;
    }
    ll p = *g[cur].begin();
    ll nxt = getE(p, cur);
    g[cur].erase(p);
    g[nxt].erase(p);
    return v[p] - DFS(nxt);
}

bitset<MAXW> dp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    v.resize(2 * n);
    e.resize(2 * n);
    g.resize(2 * n);

    rep(i, 0, 2 * n) {
        ll l, r;
        cin >> l >> r >> v[i];
        l--; r--;
        e[i] = mp(l, r + n);
        g[l].insert(i);
        g[r + n].insert(i);
    }

    vll leaves;
    rep(i, 0, 2 * n) {
        if (sz(g[i]) == 1) leaves.pb(i);
    }

    ll diff = 0;

    while (!leaves.empty()) {
        ll nxt = leaves.back();
        leaves.pop_back();
        ll p = *g[nxt].begin();
        diff += (nxt >= n) ? v[p] : -v[p];
        ll oth = getE(p, nxt);
        g[oth].erase(p);
        g[nxt].clear();

        if (sz(g[oth]) == 1) leaves.pb(oth);
    }

    rep(i, 0, 2 * n) {
        if ((sz(g[i]) != 0) && (sz(g[i]) != 2)) {
            cout << "NO" << endl;
            return 0;
        }
    }

    rep(i, 0, 2 * n) {
        if (sz(g[i])) {
            diffs.pb(llabs(DFS(i)));
        }
    }

    mll_ll w;
    rep(i, 0, sz(diffs)) {
        ll t = diffs[i];
        w[t]++;
        while (w[t] == 3) {
            w[t] -= 2;
            t *= 2;
            w[t]++;
        }
    }

    diff = llabs(diff);

    dp[0] = true;

    ll S = 0;

    for (mll_ll::iterator itr = w.begin(); itr != w.end(); itr++) {
        rep(i, 0, itr->second) {
            dp |= (dp << itr->first);
            S += itr->first;
        }
    }

    bool is_poss = false;
    rep(i, 0, MAXW) {
        is_poss |= (llabs((2 * i) - S + diff) <= k) && dp[i];
    }

    if (is_poss) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    // now we check whether we have attained a sum S in dp for which: |2 * S - diff| ≤ k

    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:21:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define rep(i, a, b) for (ll i = a; i < b; i++)
      |                                       ^
tug.cpp:104:5: note: in expansion of macro 'rep'
  104 |     rep(i, 0, sz(diffs)) {
      |     ^~~

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