結果
問題 | No.2274 三角彩色 |
ユーザー |
![]() |
提出日時 | 2023-04-14 22:08:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,201 bytes |
コンパイル時間 | 3,670 ms |
コンパイル使用メモリ | 275,196 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 12:55:09 |
合計ジャッジ時間 | 4,171 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/dsu> #include <atcoder/modint> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int64_t N; int M, B, Q; cin >> N >> M >> B >> Q; using atcoder::modint; modint::set_mod(B); vector<array<int64_t, 2>> edges(M); for (auto& [i, j] : edges) { cin >> i >> j; } vector<int64_t> U; for (auto [i, j] : edges) { U.push_back(i); U.push_back(j); } ranges::sort(U); U.erase(begin(ranges::unique(U)), end(U)); atcoder::dsu d(size(U)); modint all = 1; for (auto [i, j] : edges) { auto ti = ranges::lower_bound(U, i) - begin(U); auto tj = ranges::lower_bound(U, j) - begin(U); if (d.same(ti, tj)) { all *= 2; } else { d.merge(ti, tj); } } vector<bitset<400>> v; while (Q--) { bitset<400> cur; for (int _ = 3; _--;) { int i; cin >> i; cur[i] = 1; } for (const auto& e : v) { auto pos = e._Find_first(); if (cur[pos]) { cur ^= e; } } if (cur.any()) { v.push_back(cur); } } auto ans = modint(2).pow(size(v)); cout << (all - ans).val() << ' ' << ans.val() << '\n'; }