제출 #1320475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320475		OgradL	Tug of War (BOI15_tug)	C++20	23 / 100	62 ms	2252 KiB

tug

#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;

	vector<vector<array<int, 3>>> adj(2*N);
	vector<int> deg(2*N, 0);

	int l, r, s;
	for (int i = 0; i < 2*N; i++){
		cin >> l >> r >> s;
		--l, --r;

		r += N;

		adj[l].push_back({r, s, i});
		adj[r].push_back({l, s, i});

		deg[l]++;
		deg[r]++;
	}

	if (any_of(deg.begin(), deg.end(), [](int x){ return x == 0; })){
		cout << "NO\n";
		return 0;
	}

	queue<int> q;
	for (int i = 0; i < 2*N; i++){
		if (deg[i] == 1)
			q.push(i);
	}

	vector<int> deleted(2*N, 0);

	array<int, 2> teams = {0, 0};

	while (!q.empty()){
		int n = q.front();
		q.pop();

		deleted[n] = 1;

		int cnt = 0;
		for (auto [x, w, idx] : adj[n]){
			if (deleted[x]) continue;
			cnt++;
			deg[x]--;
			teams[n >= N] += w;
			if (deg[x] == 1){
				q.push(x);
			}
		}
		
		if (!cnt){
			cout << "NO\n";
			return 0;
		}
	}

	vector<int> cycles, used(2*N, 0);

	auto dfs = [&](auto&& dfs, int v) -> int {
		int ret = 0;
		for (auto [x, w, idx] : adj[v]){
			if (deleted[x]) continue;
			if (used[idx]) continue;
			used[idx] = 1;
			deleted[x] = 1;
			ret = w - dfs(dfs, x);
			break;
		}
		return ret;
	};

	for (int i = 0; i < 2*N; i++){
		if (!deleted[i])
			cycles.push_back(dfs(dfs, i));
	}

	if (teams[0] > teams[1])
		swap(teams[0], teams[1]);

	bitset<600001> dp;
	dp[0] = 1;

	for (int x : cycles){
		dp |= dp << abs(2*x);
		teams[1] += abs(x);
	}

	int ans = dp._Find_next(max(0, teams[1] - teams[0] - K));

	if (teams[1] - teams[0] - K <= 0)
		ans = 0;

	teams[0] += ans;
	
	if (abs(teams[0] - teams[1]) <= K && ans != dp.size()){
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}

	return 0;
}

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