Submission #726450

#	Time	Username	Problem	Language	Result	Execution time	Memory
726450		dozer	Tug of War (BOI15_tug)	C++14	100 / 100	913 ms	10304 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline") 
#pragma GCC optimize ("unroll-loops")
 
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      
#pragma GCC target("movbe")                                      
#pragma GCC target("aes,pclmul,rdrnd")                           
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

#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;
	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;
	}

	int all = abs(sum);
	vector<int> v;
	int maks = 0;
	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);
		maks = max(maks, abs(tot));
	}
	if (flag)
	{
		cout<<"NO\n";
		return 0;
	}
	
	sum = abs(sum);
	v.pb(sum);

	bitset<600005> a, b;
	a.reset(), b.reset();
	sort(v.rbegin(), v.rend());

	a[0] = 1;
	for (int i = 0; i < (int)v.size(); i++)
	{
		b |= (a<<v[i]);
		b |= (a>>v[i]);
		for (int j = 0; j <= v[i]; j++)
			b[v[i] - j] = b[v[i] - j] | a[j];
		a = b;
		b.reset();
	}
	
	for (int i = 0; i <= k; i++)
		if (a[i]) 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: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29