Submission #726440

#	Time	Username	Problem	Language	Result	Execution time	Memory
726440		dozer	Tug of War (BOI15_tug)	C++14	41 / 100	126 ms	262144 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 60005

const int modulo = 1e9 + 7;


set<int> adj[N];
int l[N], r[N], w[N], done[N];

int32_t main()
{
	fastio();


	int n, k;
	cin>>n>>k;
	int all = 0;
	for (int i = 1; i <= 2 * n; i++)
	{
		cin>>l[i]>>r[i]>>w[i];
		adj[l[i]].insert(i);
		adj[r[i] + n].insert(i);
	}

	int sum = 0;
	queue<int> q;
	for (int i = 1; i <= 2 * n; i++)
		if (adj[i].size() == 1) q.push(i);

	int flag = 0;
	while(!q.empty())
	{
		int top = q.front();
		q.pop();
		done[top] = 1;
		if (adj[top].empty())
		{
			flag = 1;
			break;
		}

		if (top <= n) sum += w[*adj[top].begin()];
		else sum -= w[*adj[top].begin()];

		for (auto i : adj[top])
		{
			int to = l[i];
			if (to == top) to = r[i] + n;
			adj[to].erase(i);
			if (adj[to].size() == 1) q.push(to);
		}
	}	

	if (flag)
	{
		cout<<"NO\n";
		return 0;
	}

	vector<int> v;
	for (int i = 1; i <= 2 * n; i++)
	{
		if (done[i]) continue;
		if (adj[i].empty())
		{
			flag = 1;
			break;
		}
		int curr = i, steps = 0, tot = 0;
		while(done[curr] == 0 && !adj[curr].empty())
		{
			done[curr] = 1;
			if (adj[curr].size() > 2)
			{
				flag = 1;
				break;
			}
			int ind = *adj[curr].begin();
			if (steps % 2) tot -= w[ind];
			else tot += w[ind];
			steps++;
			int to = l[ind];
			if (to == curr) to = r[ind] + n;
			adj[to].erase(ind);
			adj[curr].erase(ind);
			curr = to;
		}
		v.pb(abs(tot));	
		all += abs(tot);
	}
	if (flag)
	{
		cout<<"NO\n";
		return 0;
	}
	v.pb(0);
	

	int dp[v.size() + 5][all + 5];
	memset(dp, 0, sizeof(dp));
	
	sort(v.rbegin(), v.rend());
	dp[0][0] = 1;
	for (int i = 0; i < (int)v.size(); i++)
	{
		for (int j = 0; j <= all - v[i]; j++)
		{
			dp[i + 1][j + v[i]] |= dp[i][j];
			dp[i + 1][abs(j - v[i])] |= dp[i][j];
		}
	}


	sum = abs(sum);
	
	for (int i = 0; i <= all; i++)
		if (dp[v.size()][i] && min(abs(sum + i), abs(sum - i)) <= k) flag = 1;


	if (flag) cout<<"YES\n";
	else cout<<"NO\n";

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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