Submission #117150

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117150	2019-06-15T02:11:00 Z	luciocf	Tug of War (BOI15_tug)	C++14	41 / 100	249 ms	93304 KB

#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];
 
bool dp[4010][20*4010];
 
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, w = pp.ss;

		if (!mark[v])
			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});
		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;
		}
	}

	if (n > 2000)
	{
		printf("YES\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 = 1; j <= S; 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");
}

Compilation message

tug.cpp: In function 'int main()':
tug.cpp:99: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:106: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.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2048 KB	Output is correct
2	Correct	3 ms	2048 KB	Output is correct
3	Correct	4 ms	2048 KB	Output is correct
4	Correct	3 ms	2048 KB	Output is correct
5	Correct	6 ms	2048 KB	Output is correct
6	Correct	3 ms	2048 KB	Output is correct
7	Correct	3 ms	2048 KB	Output is correct
8	Correct	3 ms	2020 KB	Output is correct
9	Correct	3 ms	2048 KB	Output is correct
10	Correct	3 ms	2048 KB	Output is correct
11	Correct	3 ms	2048 KB	Output is correct
12	Correct	3 ms	2048 KB	Output is correct
13	Correct	4 ms	2048 KB	Output is correct
14	Correct	3 ms	2048 KB	Output is correct
15	Correct	3 ms	2048 KB	Output is correct
16	Correct	3 ms	2048 KB	Output is correct
17	Correct	4 ms	2048 KB	Output is correct
18	Correct	4 ms	2048 KB	Output is correct
19	Correct	4 ms	2048 KB	Output is correct
20	Correct	3 ms	2048 KB	Output is correct
21	Correct	3 ms	2048 KB	Output is correct
22	Correct	3 ms	2048 KB	Output is correct
23	Correct	3 ms	2048 KB	Output is correct
24	Correct	3 ms	2048 KB	Output is correct
25	Correct	3 ms	2048 KB	Output is correct

Subtask #2
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2048 KB	Output is correct
2	Correct	3 ms	2048 KB	Output is correct
3	Correct	4 ms	2048 KB	Output is correct
4	Correct	3 ms	2048 KB	Output is correct
5	Correct	6 ms	2048 KB	Output is correct
6	Correct	3 ms	2048 KB	Output is correct
7	Correct	3 ms	2048 KB	Output is correct
8	Correct	3 ms	2020 KB	Output is correct
9	Correct	3 ms	2048 KB	Output is correct
10	Correct	3 ms	2048 KB	Output is correct
11	Correct	3 ms	2048 KB	Output is correct
12	Correct	3 ms	2048 KB	Output is correct
13	Correct	4 ms	2048 KB	Output is correct
14	Correct	3 ms	2048 KB	Output is correct
15	Correct	3 ms	2048 KB	Output is correct
16	Correct	3 ms	2048 KB	Output is correct
17	Correct	4 ms	2048 KB	Output is correct
18	Correct	4 ms	2048 KB	Output is correct
19	Correct	4 ms	2048 KB	Output is correct
20	Correct	3 ms	2048 KB	Output is correct
21	Correct	3 ms	2048 KB	Output is correct
22	Correct	3 ms	2048 KB	Output is correct
23	Correct	3 ms	2048 KB	Output is correct
24	Correct	3 ms	2048 KB	Output is correct
25	Correct	3 ms	2048 KB	Output is correct
26	Correct	238 ms	92248 KB	Output is correct
27	Correct	36 ms	14200 KB	Output is correct
28	Correct	228 ms	91464 KB	Output is correct
29	Correct	35 ms	14208 KB	Output is correct
30	Correct	236 ms	91768 KB	Output is correct
31	Correct	38 ms	14200 KB	Output is correct
32	Correct	232 ms	92868 KB	Output is correct
33	Correct	38 ms	14208 KB	Output is correct
34	Correct	22 ms	8440 KB	Output is correct
35	Correct	38 ms	14328 KB	Output is correct
36	Correct	245 ms	92756 KB	Output is correct
37	Correct	37 ms	14328 KB	Output is correct
38	Correct	233 ms	93304 KB	Output is correct
39	Correct	36 ms	14328 KB	Output is correct
40	Correct	231 ms	92280 KB	Output is correct
41	Correct	36 ms	14328 KB	Output is correct
42	Correct	234 ms	91452 KB	Output is correct
43	Correct	38 ms	14328 KB	Output is correct
44	Correct	227 ms	91512 KB	Output is correct
45	Correct	37 ms	14200 KB	Output is correct
46	Correct	249 ms	92660 KB	Output is correct
47	Correct	8 ms	2176 KB	Output is correct
48	Correct	100 ms	38904 KB	Output is correct
49	Incorrect	96 ms	39032 KB	Output isn't correct
50	Halted	0 ms	0 KB	-

Subtask #3
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2816 KB	Output is correct
2	Correct	12 ms	2944 KB	Output is correct
3	Correct	12 ms	2816 KB	Output is correct
4	Correct	12 ms	2688 KB	Output is correct
5	Correct	12 ms	2816 KB	Output is correct
6	Correct	13 ms	2744 KB	Output is correct
7	Correct	12 ms	2944 KB	Output is correct
8	Correct	15 ms	2944 KB	Output is correct
9	Correct	13 ms	2816 KB	Output is correct
10	Correct	12 ms	2816 KB	Output is correct
11	Correct	12 ms	2944 KB	Output is correct
12	Correct	12 ms	2944 KB	Output is correct
13	Correct	12 ms	2816 KB	Output is correct
14	Correct	12 ms	2816 KB	Output is correct
15	Correct	12 ms	2816 KB	Output is correct
16	Correct	12 ms	2816 KB	Output is correct
17	Correct	12 ms	2944 KB	Output is correct
18	Correct	12 ms	2944 KB	Output is correct
19	Correct	13 ms	2944 KB	Output is correct
20	Correct	12 ms	2944 KB	Output is correct
21	Correct	13 ms	3072 KB	Output is correct
22	Correct	13 ms	3072 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2048 KB	Output is correct
2	Correct	3 ms	2048 KB	Output is correct
3	Correct	4 ms	2048 KB	Output is correct
4	Correct	3 ms	2048 KB	Output is correct
5	Correct	6 ms	2048 KB	Output is correct
6	Correct	3 ms	2048 KB	Output is correct
7	Correct	3 ms	2048 KB	Output is correct
8	Correct	3 ms	2020 KB	Output is correct
9	Correct	3 ms	2048 KB	Output is correct
10	Correct	3 ms	2048 KB	Output is correct
11	Correct	3 ms	2048 KB	Output is correct
12	Correct	3 ms	2048 KB	Output is correct
13	Correct	4 ms	2048 KB	Output is correct
14	Correct	3 ms	2048 KB	Output is correct
15	Correct	3 ms	2048 KB	Output is correct
16	Correct	3 ms	2048 KB	Output is correct
17	Correct	4 ms	2048 KB	Output is correct
18	Correct	4 ms	2048 KB	Output is correct
19	Correct	4 ms	2048 KB	Output is correct
20	Correct	3 ms	2048 KB	Output is correct
21	Correct	3 ms	2048 KB	Output is correct
22	Correct	3 ms	2048 KB	Output is correct
23	Correct	3 ms	2048 KB	Output is correct
24	Correct	3 ms	2048 KB	Output is correct
25	Correct	3 ms	2048 KB	Output is correct
26	Correct	238 ms	92248 KB	Output is correct
27	Correct	36 ms	14200 KB	Output is correct
28	Correct	228 ms	91464 KB	Output is correct
29	Correct	35 ms	14208 KB	Output is correct
30	Correct	236 ms	91768 KB	Output is correct
31	Correct	38 ms	14200 KB	Output is correct
32	Correct	232 ms	92868 KB	Output is correct
33	Correct	38 ms	14208 KB	Output is correct
34	Correct	22 ms	8440 KB	Output is correct
35	Correct	38 ms	14328 KB	Output is correct
36	Correct	245 ms	92756 KB	Output is correct
37	Correct	37 ms	14328 KB	Output is correct
38	Correct	233 ms	93304 KB	Output is correct
39	Correct	36 ms	14328 KB	Output is correct
40	Correct	231 ms	92280 KB	Output is correct
41	Correct	36 ms	14328 KB	Output is correct
42	Correct	234 ms	91452 KB	Output is correct
43	Correct	38 ms	14328 KB	Output is correct
44	Correct	227 ms	91512 KB	Output is correct
45	Correct	37 ms	14200 KB	Output is correct
46	Correct	249 ms	92660 KB	Output is correct
47	Correct	8 ms	2176 KB	Output is correct
48	Correct	100 ms	38904 KB	Output is correct
49	Incorrect	96 ms	39032 KB	Output isn't correct
50	Halted	0 ms	0 KB	-

Submission #117150

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 0 / 30.0

Subtask #3 23.0 / 23.0

Subtask #4 0 / 29.0

Subtask #1
18.0 / 18.0

Subtask #2
0 / 30.0

Subtask #3
23.0 / 23.0

Subtask #4
0 / 29.0