Submission #481997

#	Time	Username	Problem	Language	Result	Execution time	Memory
481997		pooyashams	Tug of War (BOI15_tug)	C++17	71 / 100	195 ms	17888 KiB

tug

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

const int maxn = 12e4+10;

bitset<maxn> dp;

vector<int> G[maxn];
int lfts[maxn];
int rits[maxn];
int strn[maxn];
set<int> conts[maxn];

bool vis[maxn];

int dfs(int v)
{
	vis[v] = true;
	int out = strn[v];
	for(int u: G[v])
	{
		if(vis[u]) continue;
		out -= dfs(u);
	}
	return out;
}

inline void die()
{
	cout << "NO" << endl;
	return exit(0);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k; cin >> n >> k;
	for(int i = 0; i < 2*n; i++)
	{
		cin >> lfts[i] >> rits[i] >> strn[i];
		lfts[i]--; rits[i]--;
		rits[i] += n;
		conts[lfts[i]].insert(i);
		conts[rits[i]].insert(i);
	}
	queue<int> theq;
	for(int i = 0; i < 2*n; i++)
	{
		if(conts[i].size() == 0)
			die();
		if(conts[i].size() == 1)
			theq.push(i);
	}
	int dsum = 0; // diff sum
	while(!theq.empty())
	{
		int t = theq.front(); theq.pop();
		int i = *conts[t].begin();
		int r =  lfts[i] + rits[i] - t;
		vis[i] = true;
		conts[t].erase(i);
		conts[r].erase(i);
		if(conts[r].size() == 0)
			die();
		if(conts[r].size() == 1)
			theq.push(r);
		dsum += strn[i] * ( (t/n) * 2 - 1  );
		//cerr << t << endl;
	}
	dsum = abs(dsum);
	for(int i = 0; i < 2*n; i++)
	{
		if(conts[i].size() != 2) continue;
		int x = *conts[i].begin();
		int y = *(++conts[i].begin());
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dp[0] = true;
	int tsum = 0;
	for(int v = 0; v < 2*n; v++)
	{
		if(vis[v]) continue;
		int x = abs(dfs(v));
		//cerr << x << endl;
		dp = dp | (dp << x);
		tsum += x;
	}
	bool ans = false;
	for(int i = 0; i < maxn; i++)
	{
		if(!dp[i]) continue;
		ans = ans or (abs(tsum-i-i-dsum) <= k);
		ans = ans or (abs(tsum-i-i+dsum) <= k);
	}
	if(ans)
		cout << "YES" << endl;
	else
		die();
	return 0;
}

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