Submission #1227086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227086		kaiboy	Tug of War (BOI15_tug)	C++20	0 / 100	5 ms	2632 KiB

tug

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int  N = 30000;
const int N_ = N << 1;
const int  S = N * 40;

int ii[N_], jj[N_], ww[N_], kk[S + 1];
vector<int> eh[N_]; bool visited[N_];
bool dp_[S + 1], *dp = dp_;
bool dq_[S + 1], *dq = dq_;
int qu[N_], cnt;

int dfs(int h_, int i) {
	qu[cnt++] = i;
	visited[i] = true;
	int g_ = -1;
	for (int h : eh[i])
		if (h != h_) {
			int j = i ^ ii[h] ^ jj[h];
			if (visited[j])
				g_ = g_ == -1 || g_ == h ? h : -2;
			else {
				int g = dfs(h, j);
				if (g != -1)
					g_ = g_ == -1 || g_ == g ? g : -2;
			}
		}
	return g_;
}

int dfs_(int h_, int i) {
	if (visited[i]) {
		cout << "NO\n";
		exit(0);
	}
	visited[i] = true;
	int s = 0;
	if (h_ != -1)
		s += ww[h_] * (i & 1 ? -1 : 1);
	for (int h : eh[i])
		if (h != h_ && ww[h]) {
			int j = i ^ ii[h] ^ jj[h];
			s += dfs_(h, j);
		}
	return s;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, d_; cin >> n >> d_;
	int n_ = n << 1;
	for (int h = 0; h < n_; h++) {
		int i, j, w; cin >> i >> j >> w, i--, j--;
		ii[h] = i << 1 ^ 0, jj[h] = j << 1 ^ 1, ww[h] = w;
		eh[i << 1 ^ 0].push_back(h);
		eh[j << 1 ^ 1].push_back(h);
	}
	int l_ = -d_, r_ = d_;
	for (int i = 0; i < n_; i++)
		if (!visited[i]) {
			cnt = 0;
			int h = dfs(-1, i);
			if (h < 0) {
				cout << "NO\n";
				return 0;
			}
			int w = ww[h]; ww[h] = 0;
			for (int z = 0; z < cnt; z++)
				visited[qu[z]] = false;
			int s = dfs_(-1, ii[h]) + w;
			for (int z = 0; z < cnt; z++)
				visited[qu[z]] = false;
			int t = dfs_(-1, jj[h]) - w;
			if (s > t)
				swap(s, t);
			l_ -= s, r_ -= s;
			kk[t - s]++;
		}
	dp[0] = true;
	for (int b = 0; b <= r_; b++)
		if (kk[b]) {
			for (int r = 0; r < b; r++)
				for (int k = 0, a = r; a <= r_; a += b) {
					if (dp[a])
						k++;
					dq[a] = k > 0;
					if (a >= b * kk[b] && dp[a - b * kk[b]])
						k--;
				}
			swap(dp, dq);
		}
	for (int a = r_; a >= l_ && a >= 0; a--)
		if (dp[a]) {
			cout << "YES\n";
			return 0;
		}
	cout << "NO\n";
	return 0;
}

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