Submission #1029834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029834		mat_jur	Tug of War (BOI15_tug)	C++17	100 / 100	73 ms	10620 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

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

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

	vector<vector<pair<int, int>>> g(2*n);
	vector<int> s(2*n);

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

	vector<int> last(2*n), st(2*n);
	for (int i = 0; i < 2*n; ++i) last[i] = ssize(g[i])-1;
	for (int i = 0; i < 2*n; ++i) st[i] = ssize(g[i]);

	vector<bool> off(2*n);

	int sum = 0;
	for (int i = 0; i < 2*n; ++i) {
		int j = i;
		while (st[j] == 1) {
			while (off[g[j][last[j]].se]) --last[j];
			auto [v, idx] = g[j][last[j]];
			off[idx] = true;
			sum += s[idx] * (j < n ? 1 : -1);
			--st[j]; --st[v];
			j = v;
		}
	}

	for (int i = 0; i < 2*n; ++i) {
		sort(all(g[i]), [&](pair<int, int> a, pair<int, int> b) {
			return off[a.se] < off[b.se];
		});
		auto l = g[i].begin();
		while (l != g[i].end() && !off[(*l).se]) l++;
		g[i].erase(l, g[i].end());
	}
	
	for (int i = 0; i < 2*n; ++i) {
		if (ssize(g[i]) != 2 && ssize(g[i]) != 0) {cout << "NO \n"; return 0;}
	}

	vector<bool> odw(2*n);
	vector<int> cnt(40 * n + 2);

	for (int i = 0; i < 2*n; ++i) {
		if (ssize(g[i]) == 0) continue;
		int j = i;
		int prev = -1;
		int x = 0;
		while (!odw[j]) {
			odw[j] = true;
			pair<int, int> nxt = (prev == g[j][0].fi ? g[j][1] : g[j][0]);
			x += s[nxt.se] * (j < n ? 1 : -1);	
			prev = j;
			j = nxt.fi;
		}
		if (prev != -1) {
			x = abs(x);
			cnt[2*x]++;
			sum -= x;
		}
	}

#ifndef DEBUG
	constexpr int SIZE = 1200005;
#else
	constexpr int SIZE = 20;
#endif

	debug(sum);

	bitset<SIZE> b;
	debug(cnt);

	b[0] = true;
	for (int i = 1; i < ssize(cnt); ++i) {
		while (cnt[i] >= 3 && 2*i < ssize(cnt)) {
			cnt[2*i]++;
			cnt[i] -= 2;
		}

		for (int j = 1; j <= cnt[i]; ++j) b |= (b<<i);
	}

	debug(b);
	for (int x = 0; x < SIZE; ++x) {
		if (b[x] && abs(sum+x) <= k) {
			cout << "YES \n";
			return 0;
		}
	}

	cout << "NO \n";

	return 0;
}

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