oj.uz

Submission #117121

# Submission time Handle Problem Language Result Execution time Memory
117121 2019-06-14T22:34:48 Z luciocf Tug of War (BOI15_tug) C++14
0 / 100
 309 ms 262144 KB 
#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];
 
bool dp[maxn][20*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]);
	}
 
	// solve a
	dp[0][0] = 1;
	for (int i = 1; i <= cc; i++)
	{
		for (int j = (S-2*sa)/2; j >= 1; j--)
		{
			if (pesoCycle[0][i] <= j)
				dp[i][j] |= dp[i-1][j-pesoCycle[0][i]];
			if (pesoCycle[1][i] <= j)
				dp[i][j] |= dp[i-1][j-pesoCycle[1][i]];
		}
	}
 
	int mx = -1e9;
	for (int i = 0; i <= (S-2*sa)/2; i++)
		if (dp[cc][i])
			mx = max(mx, i);
 
	if (S-2*(sa+mx) <= k)
	{
		printf("YES\n");
		return 0;
	}
 
	memset(dp, 0, sizeof dp);
 
	// solve b
	dp[0][0] = 1;
	for (int i = 1; i <= cc; i++)
	{
		for (int j = (S-2*sb)/2; j >= 1; j--)
		{
			if (pesoCycle[0][i] <= j)
				dp[i][j] |= dp[i-1][j-pesoCycle[0][i]];
			if (pesoCycle[1][i] <= j)
				dp[i][j] |= dp[i-1][j-pesoCycle[1][i]];
		}
	}
 
	mx = -1e9;
	for (int i = 0; i <= (S-2*sb)/2; i++)
		if (dp[cc][i])
			mx = max(mx, i);
 
	if (S-2*(sb+mx) <= k)
	{
		printf("YES\n");
		return 0;
	}
 
	printf("NO\n");
}

Compilation message

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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -