Submission #117353

#	Time	Username	Problem	Language	Result	Execution time	Memory
117353		luciocf	Tug of War (BOI15_tug)	C++14	100 / 100	1670 ms	6904 KiB

tug

#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
 
#define ff first
#define ss second
 
using namespace std;
 
const int maxn = 6e4+10;
const int add = 10*maxn;
 
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<1200002> dp;
 
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)
{
	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] == 0)
		{
			printf("NO\n");
			return 0;
		}
	}
 	
 	int soma = 0;
	for (int i = 1; i <= cc; i++)
	{
		markCycle(i);
		dfs2(firstCycle[i]);

		soma += (max(pesoCycle[0][i], pesoCycle[1][i])-min(pesoCycle[0][i], pesoCycle[1][i]));
	}
 
	dp[sa-sb-soma+add] = 1;
	for (int i = 1; i <= cc; i++)
	{ 
		int ss = 2*(max(pesoCycle[0][i], pesoCycle[1][i])-min(pesoCycle[0][i], pesoCycle[1][i]));
		dp |= (dp << ss);
	}
 
	for (int i = add-k; i <= add+k; i++)
	{
		if (dp[i])
		{
			printf("YES\n");
			return 0;
		}
	}
 
	printf("NO\n");
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:101: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:108: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: 29 / 29