Submission #717011

#	Time	Username	Problem	Language	Result	Execution time	Memory
717011		AmirAli_H1	Tug of War (BOI15_tug)	C++17	100 / 100	1152 ms	13984 KiB

tug

// In the name of Allah

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

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, k;
const int maxn = 6e4 + 5;
const int maxs = 6e5 + 4;
int M = 3e5 + 2;
multiset<pii> adj[maxn];
vector<pair<pii, int>> E;
bool mark[maxn]; int col[maxn], c = 1;
int D[maxn], T[maxn];
vector<int> A[maxn];
queue<int> qu;
ll res = 0;
vector<ll> vc;
bitset<maxs> dp;

void dfs(int v) {
	mark[v] = 1;
	col[v] = c; D[c] += len(adj[v]); T[c]++;
	A[c].pb(v);
	for (auto f : adj[v]) {
		auto [u, w] = f;
		if (!mark[u]) dfs(u);
	}
}

void get_res() {
	for (int i = 0; i < 2 * n; i++) {
		if (len(adj[i]) == 1) {
			qu.push(i);
		}
		else if (len(adj[i]) == 0) kill("NO");
	}
	
	while (!qu.empty()) {
		int i = qu.front(); qu.pop();
		if (mark[i]) continue;
		
		mark[i] = 1;
		auto [j, w] = *adj[i].begin();
		adj[i].clear();
		
		res += w;
		adj[j].erase(adj[j].find(Mp(i, -w)));
		if (!mark[j]) {
			if (len(adj[j]) == 1) {
				qu.push(j);
			}
			else if (len(adj[j]) == 0) kill("NO");
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++) {
		int u, v, w;
		cin >> u >> v >> w; u--; v--;
		v += n;
		adj[u].insert(Mp(v, w)); adj[v].insert(Mp(u, -w));
		E.pb(Mp(Mp(u, v), w));
	}
	
	get_res();
	
	for (int i = 0; i < 2 * n; i++) {
		if (!mark[i]) {
			dfs(i); c++;
		}
	}
	
	for (int i = 1; i < c; i++) {
		if (D[i] != 2 * T[i]) kill("NO");
		ll m = 0;
		for (int j = 0; j < len(A[i]); j++) {
			int u = A[i][j], v = A[i][(j + 1) % len(A[i])];
			for (auto f : adj[u]) {
				auto [vx, wx] = f;
				if (v == vx) {
					adj[u].erase(adj[u].find(Mp(v, wx)));
					adj[v].erase(adj[v].find(Mp(u, -wx)));
					m += wx;
					break;
				}
			}
		}
		
		vc.pb(m);
	}
	
	M += res;
	dp[M] = 1;
	for (ll val : vc) {
		ll x = abs(val);
		dp = (dp >> x) | (dp << x);
	}
	
	bool flag = 0;
	for (int i = -k - res; i <= k - res; i++) {
		if (dp[i + M] && abs(res + i) <= k) {
			flag = 1;
			break;
		}
	}
	
	if (flag) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

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