Submission #543431

#	Time	Username	Problem	Language	Result	Execution time	Memory
543431		sidon	Tug of War (BOI15_tug)	C++17	100 / 100	544 ms	10824 KiB

tug

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

// https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/BtOI/15-Tug.cpp

const int Z = 3e4, B = 20;

int n, k, p[2][2*Z], sum, s[2*Z], total;
bool vis[Z];
set<int> a[2][Z];
bitset<Z*B+1> dp;

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

	cin >> n >> k;

	for(int i = 0; i < 2*n; ++i) {
		cin >> p[0][i] >> p[1][i] >> s[i];
		total += s[i];
		for(int j : {0, 1})
			a[j][--p[j][i]].insert(i);
	}

	vector<pair<int, int>> cur[2];
	for(int j = 0; j < 2; ++j) for(int i = 0; i < n; ++i)
		if(size(a[j][i]) < 2) cur[size(a[j][i])].emplace_back(j, i);

	while(!empty(cur[1])) {
		auto [j, i] = cur[1].back(); cur[1].pop_back();
		if(empty(a[j][i])) break;

		int c = *begin(a[j][i]);
		a[j][i].erase(c);
		if(!j) sum += s[c];
 
		int o = p[!j][c];
		a[!j][o].erase(c);
		if(size(a[!j][o]) < 2) cur[size(a[!j][o])].emplace_back(!j, o);
	}

	if(!empty(cur[0])) return cout << "NO\n", 0;
	vector<int> b;

	for(int i = 0; i < n; ++i) if(size(a[0][i]) > 1 && !vis[i]) {
		int u = i, diff {};

		while(!vis[u]) {
			vis[u] = 1;
			int c = *begin(a[0][u]);
			a[0][u].erase(c);
			a[1][p[1][c]].erase(c);
			sum += s[c];

			int d = *begin(a[1][p[1][c]]);
			a[1][p[1][d]].erase(d);
			diff += s[d] - s[c];

			int v = p[0][d];
			a[0][v].erase(d);
			u = v;
		}
		b.push_back(diff);
	}

	dp[sum] = 1;
	sort(rbegin(b), rend(b));
	for(const int &i : b)
		dp |= i > 0 ? dp << i : dp >> -i;

	bool ok = 0;

	for(int i = 0; i <= Z*B; ++i) if(dp[i]) {
		int curSum = i;
		int other = total - curSum;
		if(abs(other - curSum) <= k) ok = 1;
	}

	cout << (ok ? "YES" : "NO");
}

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