Submission #115935

#	Time	Username	Problem	Language	Result	Execution time	Memory
115935		luciocf	Tug of War (BOI15_tug)	C++14	23 / 100	1947 ms	5368 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];

int freq[20*maxn];
bool dp[20*maxn];

bool mark[maxn];

vector<int> V;

vector<pii> grafo[maxn];

int msb(int x)
{
	return 31-__builtin_clz(x);
}

void dfs(int u, int p, int cc)
{
	comp[u] = cc;

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

		if (comp[v])
		{
			if (v != p)
			{
				firstCycle[cc] = u, lastCycle[cc] = v;
				back[cc] = w;
			}
			continue;
		}

		pai[v] = u, edge[v] = w;

		dfs(v, u, cc);
	}
}

void markCycle(int cc)
{
	int u = firstCycle[cc], v = lastCycle[cc];

	int s0 = 0, s1 = back[cc];
	bool turn = 0;

	while (true)
	{
		inCycle[v] = true;

		if (!turn) s0 += edge[v];
		else s1 += edge[v];

		if (u == v) break;

		v = pai[v];
		turn = !turn;
	}

	if (s0 > s1)
	{
		++freq[s1], ++freq[s0-s1];
		pesoCycle[0][cc] = s1, pesoCycle[1][cc] = s0-s1;
	}
	else
	{
		++freq[s0], ++freq[s1-s0];
		pesoCycle[0][cc] = s0, pesoCycle[1][cc] = s1-s0;
	}
}

void dfs2(int u)
{
	mark[u] = true;

	for (auto pp: grafo[u])
	{
		int v = pp.ff;
		if (!mark[v])
			dfs2(v);
	}

	if (!inCycle[u])
	{
		if (u <= n) sa += edge[u];
		else sb += edge[u];
	}
}

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});
		grafo[b].push_back({a, w});
	}

	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]);
	}

	for (int i = 0; i <= cc; i++)
	{
		int a = pesoCycle[0][i];

		int x = msb(freq[a]);

		for (int j = 0; j < x; j++)
			V.push_back((1<<j)*a);

		V.push_back(a*(freq[a]-(1<<x)+1));


		a = pesoCycle[1][i];

		x = msb(freq[a]);

		for (int j = 0; j < x; j++)
			V.push_back((1<<j)*a);

		V.push_back(a*(freq[a]-(1<<x)+1));
	}

	// solve a
	dp[0] = 1;
	for (auto w: V)
		for (int i = (S-2*sa)/2; i >= w; i--)
			dp[i] |= dp[i-w];

	int mx = 0;
	for (int i = 0; i <= (S-2*sa)/2; i++)
		if (dp[i])
			mx = max(mx, i);

	if (S-sb-2*sa-2*mx <= k)
	{
		printf("YES\n");
		return 0;
	}

	memset(dp, 0, sizeof dp);

	// solve b
	dp[0] = 1;
	for (auto w: V)
		for (int i = (S-2*sb)/2; i >= w; i--)
			dp[i] |= dp[i-w];

	mx = 0;
	for (int i = 0; i <= (S-2*sb)/2; i++)
		if (dp[i])
			mx = max(mx, i);

	if (S-sa-2*sb-2*mx <= k)
	{
		printf("YES\n");
		return 0;
	}

	printf("NO\n");
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:113: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:120: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: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29