結果

問題 No.3275 Minesweeper on Graph
ユーザー elphe
提出日時 2025-09-19 22:32:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,504 bytes
コンパイル時間 3,190 ms
コンパイル使用メモリ 281,120 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-19 22:34:13
合計ジャッジ時間 6,756 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

[[nodiscard]] static inline constexpr std::vector<uint_fast32_t> prepare(const uint_fast32_t N, [[maybe_unused]] const uint_fast32_t M, const std::vector<std::pair<uint_fast32_t, uint_fast32_t>>& edges) noexcept
{
	std::vector<uint_fast32_t> connect_mask(N, 0);
	for (const auto& [u, v] : edges)
		connect_mask[u - 1] |= UINT32_C(1) << (v - 1), connect_mask[v - 1] |= UINT32_C(1) << (u - 1);

	return connect_mask;
}

[[nodiscard]] static inline constexpr uint_fast32_t solve(const uint_fast32_t N, const std::vector<uint_fast32_t>& A, const std::vector<uint_fast32_t>& connect_mask) noexcept
{
	for (uint_fast32_t i = 0; i != (UINT32_C(1) << N); ++i)
	{
		uint_fast32_t j = 0;
		for (j = 0; j != N; ++j)
			if (std::popcount(connect_mask[j] & i) != A[j])
				break;

		if (j == N)
			return i;
	}

	return UINT_FAST32_MAX;
}

static inline void output(const uint_fast32_t N, const uint_fast32_t ans) noexcept
{
	if (ans >= (UINT32_C(1) << N))
		std::cout << "No\n";
	else
	{
		std::cout << "Yes\n" << (ans & 1);
		for (uint_fast32_t i = 1; i != N; ++i)
			std::cout << ' ' << ((ans >> i) & 1);
		std::cout << '\n';
	}
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t N, M;
	std::cin >> N >> M;
	std::vector<uint_fast32_t> A(N);
	std::vector<std::pair<uint_fast32_t, uint_fast32_t>> edges(M);
	for (auto& a : A) std::cin >> a;
	for (auto& [u, v] : edges) std::cin >> u >> v;

	output(N, solve(N, A, prepare(N, M, edges)));
	return 0;
}
0