제출 #117145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117145		luciocf	Tug of War (BOI15_tug)	C++14	18 / 100	575 ms	19064 KiB

tug

#include <bits/stdc++.h>
 
#define ff first
#define ss second
 
using namespace std;
 
const int maxn = 4e3+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[maxn];
 
bool mark[maxn];
 
vector<int> V;
 
vector<pii> grafo[maxn];

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;
	}
 
	pesoCycle[0][cc] = s0, pesoCycle[1][cc] = s1;
}
 
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]);
	}
 
	dp[0][0] = 1;
	for (int i = 1; i <= cc; i++)
	{
		for (int j = S; j >= 1; j--)
		{
			if (pesoCycle[0][i] <= j)
				dp[i][j] = dp[i][j]|dp[i-1][j-pesoCycle[0][i]];
			if (pesoCycle[1][i] <= j)
				dp[i][j] = dp[i][j]|dp[i-1][j-pesoCycle[1][i]];
		}
	}
 
	for (int i = 0; i <= S; i++)
	{
		if (dp[cc][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");
}

컴파일 시 표준 에러 (stderr) 메시지

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