Submission #536907

#	Time	Username	Problem	Language	Result	Execution time	Memory
536907		akhan42	Tug of War (BOI15_tug)	C++17	100 / 100	587 ms	13728 KiB

tug

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define lc v << 1
#define rc (v << 1) + 1

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef complex<double> cd;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX_BIT = 600 * 1000 + 5;
const int MX = 60 * 1000 + 5;
int l[MX], r[MX], s[MX];
set<int> sp2id[MX];
bool used[MX];
int n, k;


int dfs(int sp, int i, int parent) {
	used[sp] = true;
	int sp2 = sp == l[i] ? r[i] + n : l[i];
	int i2 = *sp2id[sp2].begin() == i ? *sp2id[sp2].rbegin() : *sp2id[sp2].begin();

	if(sp2 == parent)
		return ((sp < n) ? s[i] : -s[i]);

	return ((sp < n) ? s[i] : -s[i]) + dfs(sp2, i2, parent);
}


void solve() {
	cin >> n >> k;

	forn(i, 2 * n) {
		cin >> l[i] >> r[i] >> s[i];
		l[i]--; r[i]--;
		sp2id[l[i]].insert(i);
		sp2id[r[i] + n].insert(i);
	}

	set<ii> q;

	forn(sp, 2 * n) {
		q.insert({sz(sp2id[sp]), sp});
	}

	int diff = 0;
	vi diffs;

	while(!q.empty() && q.begin()->F < 2) {
		int ss = q.begin()->F, sp = q.begin()->S;
		if(ss == 0) {
			cout << "NO\n";
			return;
		}
		int i = *sp2id[sp].begin();
		int sp2 = sp == l[i] ? r[i] + n : l[i];

		q.erase({sz(sp2id[sp]), sp});
		q.erase({sz(sp2id[sp2]), sp2});

		sp2id[sp].erase(i);
		sp2id[sp2].erase(i);

		q.insert({sz(sp2id[sp2]), sp2});

		if(sp < n) {
			diff += s[i];
		}
		else {
			diff -= s[i];
		}
	}

	forn(sp, 2 * n) {
		if(!used[sp] && sz(sp2id[sp]) == 2) {
			int i = *sp2id[sp].begin();
			int j = *sp2id[sp].rbegin();
			int d1 = dfs(sp, i, sp);
			int d2 = dfs(sp, j, sp);
			if(d2 < d1)
				swap(d1, d2);

			diff += d1;
			diffs.pb(d2 - d1);
		}
	}

	bitset<MX_BIT> b;
	b[0] = 1;
	for(int d: diffs) {
		b |= b << d;
	}

	for(int s = b._Find_first(); s < sz(b); s = b._Find_next(s)) {
		if(abs(diff + s) <= k) {
			cout << "YES\n";
			return;
		}
	}

	cout << "NO\n";
}


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

//	freopen("triangles.in", "r", stdin);
//	freopen("triangles.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

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