oj.uz

답안 #681966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681966 2023-01-15T00:14:32 Z MilosMilutinovic Tug of War (BOI15_tug) C++14
0 / 100
 455 ms 10404 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(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];
			assert(abs(S00 - S01) <= 1);
			assert(abs(S10 - S11) <= 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 7124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 7124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 5708 KB Output is correct
2 Correct 12 ms 5204 KB Output is correct
3 Correct 378 ms 5704 KB Output is correct
4 Correct 11 ms 5076 KB Output is correct
5 Correct 383 ms 5700 KB Output is correct
6 Correct 11 ms 5076 KB Output is correct
7 Correct 426 ms 5720 KB Output is correct
8 Correct 10 ms 5076 KB Output is correct
9 Correct 399 ms 5716 KB Output is correct
10 Correct 15 ms 5076 KB Output is correct
11 Correct 413 ms 5708 KB Output is correct
12 Correct 10 ms 5076 KB Output is correct
13 Correct 455 ms 5704 KB Output is correct
14 Correct 366 ms 5716 KB Output is correct
15 Correct 11 ms 5076 KB Output is correct
16 Correct 419 ms 5708 KB Output is correct
17 Correct 10 ms 5076 KB Output is correct
18 Correct 361 ms 5804 KB Output is correct
19 Correct 10 ms 5076 KB Output is correct
20 Correct 429 ms 5716 KB Output is correct
21 Correct 12 ms 5588 KB Output is correct
22 Runtime error 16 ms 10404 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 7124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -