oj.uz

Submission #681967

# Submission time Handle Problem Language Result Execution time Memory
681967 2023-01-15T00:17:52 Z MilosMilutinovic Tug of War (BOI15_tug) C++14
0 / 100
 585 ms 10072 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int N = 30333;
int n, k;
int l[2 * N];
int r[2 * N];
int s[2 * N];
vector<int> g[4 * N];
int ver;
int pos;
bool was[4 * N];
ll sum[2];
vector<int> comp;
bool have[4 * N];
bool taken[4 * N];
bitset<40 * N + 1> dp;

void addEdge(int v, int u) {
	g[v].push_back(u);
	g[u].push_back(v);
}

void dfs(int v) {
	if (v < 2 * n) {
		sum[ver & 1] += s[v];
		ver++;
	} else pos++;
	was[v] = true;
	comp.push_back(v);
	for (int u : g[v])
		if (!was[u])
			dfs(u);
}

bool OK;
void Go(int p) {
	taken[p] = true;
	for (int x : g[p]) {
		if (!have[x]) {
			assert((p == 2 * n + l[x]) || (p == (3 * n + r[x])));
			int w = (p ^ (2 * n + l[x]) ^ (3 * n + r[x]));
			if (taken[w])
				OK = false;
			else {
				sum[(w < 3 * n)] += s[x];
				taken[w] = true;
				have[x] = true;
				Go(w);
			}
		}
	}
}

bool Try(int i, int p) {
	OK = true;
	for (int it : comp) {
		have[it] = false;
		taken[it] = false;
	}
	sum[0] = 0;
	sum[1] = 0;
	sum[(p < 3 * n)] += s[i];
	have[i] = true;
	Go(p);
	return OK;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &k);
	assert(k >= 0);
	for (int i = 0; i < 2 * n; i++) {
		scanf("%d%d%d", &l[i], &r[i], &s[i]);
		--l[i];--r[i];
		addEdge(i, 2 * n + l[i]);
		addEdge(i, 3 * n + r[i]);
	}
	vector<pair<int, int>> canSame;
	vector<int> mustDiff;
	for (int i = 0; i < 2 * n; i++) if (!was[i]) {
		ver = 0;
		pos = 0;
		sum[0] = 0;
		sum[1] = 0;
		comp.clear();
		dfs(i);
		if (ver > pos) {
			printf("NO\n");
			return 0;
		}
		assert(ver == pos);
		assert(Try(i, 3 * n + r[i]) || Try(i, 2 * n + l[i]));
		if (!Try(i, 3 * n + r[i])) {
			assert(Try(i, 2 * n + l[i]));
			mustDiff.push_back(sum[0] - sum[1]);
		} else if (!Try(i, 2 * n + l[i])) {
			assert(Try(i, 3 * n + r[i]));
			mustDiff.push_back(sum[0] - sum[1]);
		} else {
			assert(Try(i, 2 * n + l[i]));
			int S00 = sum[0];
			int S01 = sum[1];
			assert(Try(i, 3 * n + r[i]));
			int S10 = sum[0];
			int S11 = sum[1];
			canSame.push_back({S00 - S01, S10 - S11});
		}
	}
	dp[20 * N] = 1;
	for (auto x : canSame) {
		int a = x.first;
		int b = x.second;
		if (a >= 0 && b >= 0) {
			dp = ((dp << a) | (dp << b));
		} else if (a < 0 && b >= 0) {
			dp = ((dp >> (-a)) | (dp << b));
		} else if (a >= 0 && b < 0) {
			dp = ((dp << a) | (dp >> (-b)));
		} else {
			dp = ((dp >> (-a)) | (dp >> (-b)));
		}

	}
	for (int x : mustDiff) {
		if (x < 0)
			dp = (dp >> (-x));
		else
			dp = (dp << x);
	}
	bool ok = false;
	for (int i = 0; i <= k; i++)
		if (dp[20 * N + i] || dp[20 * N - i])
			ok = true;
	if (ok)
		printf("YES\n");
	else
		printf("NO\n");

	return 0;
}

Compilation message

tug.cpp: In function 'int main()':
tug.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d%d%d", &l[i], &r[i], &s[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 3 ms 3796 KB Output is correct
6 Correct 2 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 4 ms 3796 KB Output is correct
9 Correct 3 ms 3796 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 3 ms 3796 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct
14 Correct 2 ms 3796 KB Output is correct
15 Correct 2 ms 3796 KB Output is correct
16 Correct 2 ms 3796 KB Output is correct
17 Correct 3 ms 3796 KB Output is correct
18 Correct 4 ms 3916 KB Output is correct
19 Correct 3 ms 3796 KB Output is correct
20 Correct 3 ms 3796 KB Output is correct
21 Correct 2 ms 3540 KB Output is correct
22 Correct 2 ms 3796 KB Output is correct
23 Incorrect 2 ms 3796 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 3 ms 3796 KB Output is correct
6 Correct 2 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 4 ms 3796 KB Output is correct
9 Correct 3 ms 3796 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 3 ms 3796 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct
14 Correct 2 ms 3796 KB Output is correct
15 Correct 2 ms 3796 KB Output is correct
16 Correct 2 ms 3796 KB Output is correct
17 Correct 3 ms 3796 KB Output is correct
18 Correct 4 ms 3916 KB Output is correct
19 Correct 3 ms 3796 KB Output is correct
20 Correct 3 ms 3796 KB Output is correct
21 Correct 2 ms 3540 KB Output is correct
22 Correct 2 ms 3796 KB Output is correct
23 Incorrect 2 ms 3796 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 5704 KB Output is correct
2 Correct 10 ms 5076 KB Output is correct
3 Correct 417 ms 5704 KB Output is correct
4 Correct 11 ms 5076 KB Output is correct
5 Correct 585 ms 5712 KB Output is correct
6 Correct 12 ms 5076 KB Output is correct
7 Correct 482 ms 5708 KB Output is correct
8 Correct 11 ms 5076 KB Output is correct
9 Correct 540 ms 5716 KB Output is correct
10 Runtime error 13 ms 10072 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 3 ms 3796 KB Output is correct
6 Correct 2 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 4 ms 3796 KB Output is correct
9 Correct 3 ms 3796 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 3 ms 3796 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct
14 Correct 2 ms 3796 KB Output is correct
15 Correct 2 ms 3796 KB Output is correct
16 Correct 2 ms 3796 KB Output is correct
17 Correct 3 ms 3796 KB Output is correct
18 Correct 4 ms 3916 KB Output is correct
19 Correct 3 ms 3796 KB Output is correct
20 Correct 3 ms 3796 KB Output is correct
21 Correct 2 ms 3540 KB Output is correct
22 Correct 2 ms 3796 KB Output is correct
23 Incorrect 2 ms 3796 KB Output isn't correct
24 Halted 0 ms 0 KB -