제출 #1270671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270671		BuzzyBeez	Tug of War (BOI15_tug)	C++20	100 / 100	141 ms	82760 KiB

tug

#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,lzcnt")
#include <bits/stdc++.h> 
using namespace std;

const int N = 6e4;

int s[N + 8]; 
vector<pair<int, int>> adj[N + 8];
int a[N + 8], b[N + 8]; pair<int, int> par[N + 8];
int tin[N + 8]; bool mark[N + 8];

void add_edge(int u, int v, int id) {
	adj[u].emplace_back(v, id);
	adj[v].emplace_back(u, id);
	// cout << u << ' ' << v << ' ' << id << endl;
}

int timer = 0; vector<pair<int, int>> cycle;
void DFS(int u, int p_id) {
	tin[u] = ++timer;
	int v, id;
	for (pair<int, int> edge : adj[u]) if (edge.second != p_id) {
		tie(v, id) = edge;
		if (!tin[v]) par[v] = {u, id}, DFS(v, id);
		else if (tin[v] < tin[u]) {
			int t = u; cycle = {{u, id}};
			while (t != v) {
				cycle.push_back(par[t]);
				t = par[t].first;
			}
			for (pair<int, int> p : cycle) mark[p.first] = 1;
		}
	}
}

int n, m = 0;
void DFS_subtree(int u, int p) {
	int v, id;
	for (pair<int, int> edge : adj[u]) if (edge.first != p && !mark[edge.first]) {
		tie(v, id) = edge;
		a[m] += (v <= n ? s[id] : 0);
		b[m] += (v <= n ? s[id] : 0);
		DFS_subtree(v, u);
	}
}

void process_cycle() {
	// cout << ">> ";
	// for (pair<int, int> p : cycle) cout << p.first << ' ';
	// cout << endl;
	for (pair<int, int> p : cycle) DFS_subtree(p.first, 0);
	int sz = cycle.size(), u, v, id;
	for (int i = 0; i < sz; ++i) {
		u = cycle[i].first; v = cycle[(i + 1) % sz].first; id = cycle[i].second;
		a[m] += (v <= n ? s[id] : 0);
		b[m] += (u <= n ? s[id] : 0);
		// cout << ">>> " << u << ' ' << v << " -> " << a[m] << ' ' << b[m] << endl;
	}
}

const int N2 = 6e5;

int f[N2 + 8], c[1608];
vector<bitset<N2 + 8>> dp;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int k, l, r; cin >> n >> k;
	for (int i = 1; i <= n + n; ++i) {
		cin >> l >> r >> s[i];
		add_edge(l, r + n, i);
	}
	for (int i = 1; i <= n + n; ++i) if (!tin[i]) {
		++m;
		DFS(i, 0);
		process_cycle();
	}
	// for (int i = 1; i <= m; ++i) cout << a[i] << ' ';
	// cout << endl;
	// for (int i = 1; i <= m; ++i) cout << b[i] << ' ';
	// cout << endl;
	int tot = accumulate(s + 1, s + n + n + 1, 0), base = 0;
	for (int i = 1; i <= m; ++i) base += min(a[i], b[i]), ++f[abs(a[i] - b[i])];
	m = 0; int p;
	for (int i = 1; i <= N2; ++i) if (f[i]) {
		p = 1;
		while (f[i] >= p) {
			c[++m] = i * p;
			f[i] -= p;
			p <<= 1;
		}
		if (f[i]) {
			c[++m] = i * f[i];
			f[i] = 0;
		}
	}
	// for (int i = 1; i <= m; ++i) cout << c[i] << ' ';
	// cout << endl;
	dp.resize(m + 1); dp[0][0] = 1;
	for (int i = 1; i <= m; ++i) dp[i] = (dp[i - 1] | (dp[i - 1] << c[i]));
	for (int i = base; i <= tot; ++i) if (dp[m][i - base] && abs(i + i - tot) <= k) {
		cout << "YES\n";
		return 0;
	} 
	cout << "NO";
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29