oj.uz

Submission #1029826

# Submission time Handle Problem Language Result Execution time Memory
1029826 2024-07-21T11:38:05 Z mat_jur Tug of War (BOI15_tug) C++17
0 / 100
 8 ms 3932 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, k;
	cin >> n >> k;

	vector<vector<pair<int, int>>> g(2*n);
	vector<int> s(2*n);

	int S = 0;
	for (int i = 0; i < 2*n; ++i) {
		int l, r;
		cin >> l >> r >> s[i];
		S += s[i];
		--l;
		r += n-1;
		g[l].eb(mp(r, i));
		g[r].eb(mp(l, i));
	}

	vector<int> last(2*n), st(2*n);
	for (int i = 0; i < 2*n; ++i) last[i] = ssize(g[i])-1;
	for (int i = 0; i < 2*n; ++i) st[i] = ssize(g[i]);

	vector<bool> off(2*n);

	int sum = 0;
	for (int i = 0; i < 2*n; ++i) {
		int j = i;
		while (st[j] == 1) {
			while (off[g[j][last[j]].se]) --last[j];
			auto [v, idx] = g[j][last[j]];
			off[idx] = true;
			sum += s[idx] * (j < n ? 1 : -1);
			--st[j]; --st[v];
			j = v;
		}
	}

	for (int i = 0; i < 2*n; ++i) {
		sort(all(g[i]), [&](pair<int, int> a, pair<int, int> b) {
			return off[a.se] < off[b.se];
		});
		auto l = g[i].begin();
		while (l != g[i].end() && !off[(*l).se]) l++;
		g[i].erase(l, g[i].end());
	}

	vector<bool> odw(2*n);
	vector<int> cnt(40 * n + 2);

	for (int i = 0; i < 2*n; ++i) {
		if (ssize(g[i]) == 0) continue;
		int j = i;
		int prev = -1;
		int x = 0;
		while (!odw[j]) {
			odw[j] = true;
			pair<int, int> nxt = (prev == g[j][0].fi ? g[j][1] : g[j][0]);
			x += s[nxt.se] * (j < n ? 1 : -1);	
			prev = j;
			j = nxt.fi;
		}
		if (prev != -1) {
			x = abs(x);
			cnt[2*x]++;
			sum -= x;
		}
	}

#ifndef DEBUG
	constexpr int SIZE = 1200005;
#else
	constexpr int SIZE = 20;
#endif

	debug(sum);

	bitset<SIZE> b;
	debug(cnt);

	b[0] = true;
	for (int i = 1; i < ssize(cnt); ++i) {
		while (cnt[i] >= 3 && 2*i < ssize(cnt)) {
			cnt[2*i]++;
			cnt[i] -= 2;
		}

		for (int j = 1; j <= cnt[i]; ++j) b |= (b<<i);
	}

	debug(b);
	for (int x = 0; x < SIZE; ++x) {
		if (b[x] && abs(sum+x) <= k) {
			cout << "YES \n";
			return 0;
		}
	}

	cout << "NO \n";

	return 0;
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3932 KB Output is correct
2 Incorrect 8 ms 3932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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