#1185299 (C++23) No.3695 同室と別室

• 問題: No.3695 同室と別室
• ユーザー: こめだわら
• 提出日時: 2026-09-09 21:23:14
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 33 ms / 2,000 ms
• コード長: 6,600 bytes
• コンパイル時間: 2,227 ms
• コンパイル使用メモリ: 342,624 KB
• 実行使用メモリ: 29,824 KB
• 最終ジャッジ日時: 2026-09-09 21:23:18
• 合計ジャッジ時間: 4,112 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 13

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    return os<<p.first<<' '<<p.second;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#ifndef LIBRARY_DATA_STRUCTURE_DSU_HPP
#define LIBRARY_DATA_STRUCTURE_DSU_HPP

#line 1 "src/data-structure/dsu.hpp"


#include <vector>
#include <numeric>
#include <algorithm>

struct dsu {
  public:
    dsu() : _n(0) {}
    /// n 頂点の Union-Find を作る。
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    /// a と b を同じ集合にまとめ、代表元を返す。
    int merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    /// a と b が同じ集合なら true。
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    /// a が属する集合の代表元を返す。
    int leader(int a) {
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    /// a が属する集合のサイズを返す。
    int size(int a) {
        return -parent_or_size[leader(a)];
    }

    /// 全ての連結成分を頂点リストとして返す。
    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // 負の値の場合：自身が根であり、その絶対値が連結成分のサイズ
    // 正の値の場合：親のインデックス
    std::vector<int> parent_or_size;
};

#endif  // LIBRARY_DATA_STRUCTURE_DSU_HPP

#ifndef LIBRARY_MATH_MODINT_HPP
#define LIBRARY_MATH_MODINT_HPP

#line 1 "src/math/modint.hpp"


#include <iostream>

template <int MOD>
struct static_modint {
    using mint = static_modint;

  private:
    int _v;

  public:
    static_modint() : _v(0) {}

    template <class T>
    static_modint(T v) {
        long long x = (long long)(v % MOD);
        if (x < 0) x += MOD;
        _v = int(x);
    }

    /// 0 以上 mod 未満の整数値を返す。
    int val() const { return _v; }
    /// 法 MOD を返す。
    static constexpr int mod() { return MOD; }

    /// 0 <= v < mod を満たす値を、剰余を取らずに構築する。
    static mint raw(int v) {
        mint res;
        res._v = v;
        return res;
    }

    /// n 乗を返す。n >= 0。
    mint pow(long long n) const {
        mint res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    /// 逆元を返す。MOD は素数で、値は 0 でないこと。
    mint inv() const {
        return pow(MOD - 2);
    }

    mint& operator+=(const mint& a) {
        _v += a._v;
        if (_v >= MOD) _v -= MOD;
        return *this;
    }

    mint& operator-=(const mint& a) {
        _v -= a._v;
        if (_v < 0) _v += MOD;
        return *this;
    }

    mint& operator*=(const mint& a) {
        _v = int((long long)_v * a._v % MOD);
        return *this;
    }

    mint& operator/=(const mint& a) {
        return *this *= a.inv();
    }

    mint operator+() const { return *this; }
    mint operator-() const { return mint(0) - *this; }

    friend mint operator+(const mint& a, const mint& b) { return mint(a) += b; }
    friend mint operator-(const mint& a, const mint& b) { return mint(a) -= b; }
    friend mint operator*(const mint& a, const mint& b) { return mint(a) *= b; }
    friend mint operator/(const mint& a, const mint& b) { return mint(a) /= b; }
    friend bool operator==(const mint& a, const mint& b) { return a._v == b._v; }
    friend bool operator!=(const mint& a, const mint& b) { return a._v != b._v; }
    friend std::ostream& operator<<(std::ostream& os, const mint& a) { return os << a._v; }
    friend std::istream& operator>>(std::istream& is, mint& a) {
        long long v;
        is >> v;
        a = mint(v);
        return is;
    }
};

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

using mint = modint998244353;

#endif  // LIBRARY_MATH_MODINT_HPP


void solve() {
    ll N,Q;
    cin>>N>>Q;
    dsu uf(2*N);
    rep(i,Q){
        ll t,a,b;
        cin>>t>>a>>b;
        a--;
        b--;
        if (t==0){
            if (uf.same(a,b+N)){
                cout<<0<<'\n';
                return;
            }
            uf.merge(a,b);
            uf.merge(a+N,b+N);
        }
        else{
            if (uf.same(a,b)){
                cout<<0<<'\n';
                return;
            }
            uf.merge(a,b+N);
            uf.merge(a+N,b);
        }
    }
    ll g=uf.groups().size();
    mint ans=mint(2).pow(g/2);
    cout<<ans<<'\n';
    return;
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T=1;
    while (T--){
        solve();
    }
    return 0;
}