Submission #49105

#	Time	Username	Problem	Language	Result	Execution time	Memory
49105		aome	Tug of War (BOI15_tug)	C++17	100 / 100	647 ms	41368 KiB

tug

#include <bits/stdc++.h>

using namespace std;

const int N = 30005;

int n, m, sum;
int a[2  * N];
int deg[4 * N];
int par[4 * N];
int b[20 * N];
int f[20 * N];
bool vis[4 * N];
vector<int> G[4 * N];
vector<int> vec[4 * N];

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

void join(int u, int v) { par[find(u)] = find(v); }

void add(int u, int v) {
	// cout << u << ' ' << v << '\n';
	deg[u]++, deg[v]++, G[u].push_back(v), G[v].push_back(u), join(u, v);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= 4 * n; ++i) par[i] = i;
	for (int i = 1; i <= 2 * n; ++i) {
		int l, r; cin >> l >> r >> a[i];
		add(i, l + 2 * n), add(i, r + 3 * n);
	}
	for (int i = 1; i <= 4 * n; ++i) vec[find(i)].push_back(i);
	for (int i = 1; i <= 4 * n; ++i) {
		if (i != find(i)) continue;
		int cnt = 0;
		for (auto j : vec[i]) cnt += deg[j];
		if (cnt != vec[i].size() * 2) {
			cout << "NO"; return 0; 
		} 
	}
	queue<int> qu;
	for (int i = 1; i <= 4 * n; ++i) {
		if (deg[i] == 1) qu.push(i);
	}
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			deg[v]--;
			if (deg[v] == 1) {
				if (v <= n * 2) {
					if (u > 3 * n) sum += a[v];
					else sum -= a[v];
				}
				qu.push(v);
			}
		}
	}
	for (int i = 1; i <= 2 * n; ++i) {
		if (deg[i] != 2 || vis[i]) continue;
		int cur = i;
		vector<int> cir;
		while (1) {
			bool found = 0;
			vis[cur] = 1, cir.push_back(cur);
			for (auto j : G[cur]) {
				if (!vis[j] && deg[j] == 2) {
					cur = j, found = 1;
				}
			}
			if (!found) break;
		}
		int tmp = 0;
		for (int j = 0; j < cir.size(); j += 2) {
			if (j % 4 == 0) tmp += a[cir[j]];
			else tmp -= a[cir[j]]; 
		}
		if (tmp < 0) tmp = -tmp;
		// cout << tmp << '\n';
		sum += tmp, b[tmp]++;
	}
	f[0] = 1;
	int lim = 0;
	for (int i = 1; i <= 20 * n; ++i) {
		if (!b[i]) continue;
		for (int j = 0; j <= lim; ++j) {
			if (f[j]) f[j] = b[i] + 1;
		}
		lim += b[i] * i;
		for (int j = 0; j <= lim - i; ++j) {
			f[j + i] = max(f[j + i], f[j] - 1);
		}
	}
	for (int i = 0; i <= lim; ++i) {
		// if (f[i]) cout << i << '\n';
		if (f[i] && abs(sum - 2 * i) <= m) {
			cout << "YES"; return 0;
		} 
	}
	cout << "NO";
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cnt != vec[i].size() * 2) {
       ~~~~^~~~~~~~~~~~~~~~~~~~
tug.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < cir.size(); j += 2) {
                   ~~^~~~~~~~~~~~

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