Submission #117292

#	Time	Username	Problem	Language	Result	Execution time	Memory
117292		luciocf	Tug of War (BOI15_tug)	C++14	71 / 100	3062 ms	5336 KiB

tug

#include <bits/stdc++.h>
 
#define ff first
#define ss second
 
using namespace std;
 
const int maxn = 6e4+10;
 
typedef pair<int, int> pii;
 
int n, k;
 
int sa, sb;
 
int pai[maxn], edge[maxn];
 
int firstCycle[maxn], lastCycle[maxn], pesoCycle[2][maxn], inCycle[maxn];
int comp[maxn], back[maxn];
 
bitset<20*maxn> dp[2];
 
bool mark[maxn];
 
vector<int> V;
 
vector<pair<pii, int>> grafo[maxn];

void dfs(int u, int ant, int cc)
{
	comp[u] = cc;
 
	for (auto pp: grafo[u])
	{
		int v = pp.ff.ff, w = pp.ff.ss, e = pp.ss;
 
		if (comp[v] == cc)
		{
			if (ant == e) continue;

			firstCycle[cc] = u, lastCycle[cc] = v;
			back[cc] = w;

			continue;
		}
 
		pai[v] = u, edge[v] = w;
 
		dfs(v, e, cc);
	}
}
 
void markCycle(int cc)
{
	int v = lastCycle[cc];
 
	int s0 = 0, s1 = back[cc];
	bool turn = 0;
 
	while (true)
	{
		inCycle[v] = true;
 
		if (v == firstCycle[cc]) break;

		if (!turn) s0 += edge[v];
		else s1 += edge[v];
 
		v = pai[v];
		turn = !turn;
	}
 
	pesoCycle[0][cc] = s0, pesoCycle[1][cc] = s1;
}

void dfs2(int u)
{
	mark[u] = true;
 
	for (auto pp: grafo[u])
	{
		int v = pp.ff.ff, w = pp.ff.ss;

		if (mark[v]) continue;

		dfs2(v);

		if (!inCycle[v])
		{
			if (v <= n) sa += w;
			else sb += w; 
		}
	}
}
 
int main(void)
{
	memset(firstCycle, -1, sizeof firstCycle);
 
	scanf("%d %d", &n, &k);

	int S = 0;
 
	for (int i = 1; i <= 2*n; i++)
	{
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
 
		b += n;
		S += w;
 
		grafo[a].push_back({{b, w}, i});
		grafo[b].push_back({{a, w}, i});
	}
 
	int cc = 0;
	for (int i = 1; i <= 2*n; i++)
	{
		if (comp[i]) continue;
 
		dfs(i, 0, ++cc);
 
		if (firstCycle[cc] == -1)
		{
			printf("NO\n");
			return 0;
		}
	}

	for (int i = 1; i <= cc; i++)
	{
		markCycle(i);
		dfs2(firstCycle[i]);
	}
 
	dp[0][0] = 1;
	for (int i = 1; i <= cc; i++)
	{
		int a = (i-1)%2, b = i%2;

		dp[b].reset();

		for (int j = S; j >= 1; j--)
		{
			if (pesoCycle[0][i] <= j)
				dp[b][j] = dp[b][j]|dp[a][j-pesoCycle[0][i]];

			if (pesoCycle[1][i] <= j)
				dp[b][j] = dp[b][j]|dp[a][j-pesoCycle[1][i]];
		}
	}

	for (int i = 1; i <= S; i++)
	{
		if (dp[cc%2][i])
		{
			int a = i+sa, b = S-i-sa;

			if (abs(a-b) <= k)
			{
				printf("YES\n");
				return 0;
			}

			a = S-i-sb, b = i+sb;
			
			if (abs(a-b) <= k)
			{
				printf("YES\n");
				return 0;
			}
		}
	}
 
	printf("NO\n");
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
tug.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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