Submission #658612

#	Time	Username	Problem	Language	Result	Execution time	Memory
658612		Shahrad	Tug of War (BOI15_tug)	C++17	41 / 100	77 ms	6612 KiB

tug

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

#define ll long long
#define int ll
#define all(x) x.begin(),x.end()
#define sz size()
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define pii pair<int,int>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

const int N = 1e5 + 5, M = 2e6, M2 = 2 * M;

vector <pii> adj[N];
int s[N], cnt[M2];
bool vis[N];
int ans, wef, few, q;
bitset <M2> bs;

void dfs (int v, int b, int par)
{
	wef++;
	vis[v] = 1;
	few += adj[v].sz;
	for (pii u : adj[v])
	{
		if ((!vis[u.F] || !q) && u.S != par)
		{
			if (vis[u.F])
			{
				q = 1;
				if (!b)
					ans += s[u.S];
				else
					ans -= s[u.S];
				continue;
			}
			if (!b)
				ans += s[u.S];
			else
				ans -= s[u.S];
			dfs (u.F, 1 - b, u.S);
		}
	}
}

void Solve ()
{
	int n, k, l, r;
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++)
	{
		cin >> l >> r >> s[i];
		r += n;
		l--, r--;
		adj[l].pb (mk (r, i));
		adj[r].pb (mk (l, i));
	}
	for (int i = 0; i < 2 * n; i++)
	{
		if (!vis[i])
		{
			wef = few = ans = q = 0;
			dfs (i, 0, -1);
			if (few != wef * 2)
			{
				cout << "NO" << endl;
				return;
			}
			cnt[abs (ans)]++;
		}
	}
	bs[M] = 1;
	for (int i = 1; i < M2; i++)
	{
		while (cnt[i] > 2)
		{
			cnt[i] -= 2;
			cnt[i * 2]++;
		}
		for (int j = 0; j < cnt[i]; j++)
			bs = (bs << i) | (bs >> i);
	}
	for (int i = M; i <= M + k; i++)
		if (bs[i])
		{
			cout << "YES" << endl;
			return;
		}
	cout << "NO" << endl;
}

int32_t main ()
{
	ios::sync_with_stdio(0), cin.tie (0), cin.tie (0);
	int tt = 1;
//      cin >> tt;
	while (tt--)
		Solve ();
}

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