結果

問題 No.2293 無向辺 2-SAT
ユーザー dyktr_06dyktr_06
提出日時 2023-05-05 23:28:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 966 ms / 4,000 ms
コード長 10,926 bytes
コンパイル時間 4,283 ms
コンパイル使用メモリ 271,508 KB
実行使用メモリ 75,224 KB
最終ジャッジ日時 2024-05-02 18:50:17
合計ジャッジ時間 41,145 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 480 ms
30,376 KB
testcase_04 AC 911 ms
75,096 KB
testcase_05 AC 920 ms
74,972 KB
testcase_06 AC 966 ms
73,304 KB
testcase_07 AC 43 ms
5,376 KB
testcase_08 AC 907 ms
72,144 KB
testcase_09 AC 515 ms
47,680 KB
testcase_10 AC 519 ms
47,548 KB
testcase_11 AC 930 ms
75,224 KB
testcase_12 AC 873 ms
72,152 KB
testcase_13 AC 854 ms
72,144 KB
testcase_14 AC 571 ms
56,892 KB
testcase_15 AC 447 ms
50,616 KB
testcase_16 AC 910 ms
75,092 KB
testcase_17 AC 940 ms
74,584 KB
testcase_18 AC 914 ms
74,332 KB
testcase_19 AC 384 ms
38,588 KB
testcase_20 AC 571 ms
46,264 KB
testcase_21 AC 544 ms
43,200 KB
testcase_22 AC 588 ms
46,780 KB
testcase_23 AC 607 ms
47,032 KB
testcase_24 AC 638 ms
47,036 KB
testcase_25 AC 601 ms
47,032 KB
testcase_26 AC 591 ms
47,292 KB
testcase_27 AC 609 ms
47,036 KB
testcase_28 AC 586 ms
47,040 KB
testcase_29 AC 743 ms
46,908 KB
testcase_30 AC 868 ms
46,912 KB
testcase_31 AC 591 ms
47,424 KB
testcase_32 AC 344 ms
27,692 KB
testcase_33 AC 361 ms
27,696 KB
testcase_34 AC 359 ms
27,692 KB
testcase_35 AC 356 ms
27,820 KB
testcase_36 AC 364 ms
27,696 KB
testcase_37 AC 354 ms
27,692 KB
testcase_38 AC 357 ms
27,652 KB
testcase_39 AC 367 ms
27,816 KB
testcase_40 AC 334 ms
27,820 KB
testcase_41 AC 195 ms
14,308 KB
testcase_42 AC 288 ms
21,544 KB
testcase_43 AC 346 ms
26,304 KB
testcase_44 AC 460 ms
37,196 KB
testcase_45 AC 487 ms
39,612 KB
testcase_46 AC 509 ms
42,172 KB
testcase_47 AC 530 ms
43,836 KB
testcase_48 AC 559 ms
44,992 KB
testcase_49 AC 556 ms
45,884 KB
testcase_50 AC 606 ms
46,524 KB
testcase_51 AC 606 ms
47,164 KB
testcase_52 AC 613 ms
47,676 KB
testcase_53 AC 609 ms
48,952 KB
testcase_54 AC 619 ms
50,492 KB
testcase_55 AC 625 ms
54,076 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(int i = 0; i < (int)(n); ++i)
#define rep2(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep3(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep4(i, a, b, c) for(int i = (a); i < (int)(b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()
#define Sort(a) sort(a.begin(), a.end())
#define RSort(a) sort(a.rbegin(), a.rend())

typedef long long int ll;
typedef unsigned long long ul;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef vector<string> vst;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef pair<long long, long long> P;

template<class T> long long sum(const T& a){ return accumulate(a.begin(), a.end(), 0LL); }
template<class T> auto min(const T& a){ return *min_element(a.begin(), a.end()); }
template<class T> auto max(const T& a){ return *max_element(a.begin(), a.end()); }

const long long MINF = 0x7fffffffffff;
const long long INF = 0x1fffffffffffffff;
const long long MOD = 998244353;
const long double EPS = 1e-9;
const long double PI = acos(-1);
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p){ is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for(T &in : v) is >> in; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v){ for(int i = 0; i < (int) v.size(); ++i){ os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp){ for(auto &[key, val] : mp){ os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, queue<T> q){ while(q.size()){ os << q.front() << " "; q.pop(); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q){ while(q.size()){ os << q.front() << " "; q.pop_front(); } return os; }
template <typename T> ostream &operator<<(ostream &os, stack<T> st){ while(st.size()){ os << st.top() << " "; st.pop(); } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq){ while(pq.size()){ os << pq.top() << " "; pq.pop(); } return os; }

template<class T, class U> inline T vin(T& vec, U n) { vec.resize(n); for(int i = 0; i < (int) n; ++i) cin >> vec[i]; return vec; }
template<class T> inline void vout(T vec, string s = "\n"){ for(auto x : vec) cout << x << s; }
template<class... T> void in(T&... a){ (cin >> ... >> a); }
void out(){ cout << '\n'; }
template<class T, class... Ts> void out(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; }
template<class T, class U> void inGraph(vector<vector<T>>& G, U n, U m, bool directed = false){ G.resize(n); for(int i = 0; i < m; ++i){ int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); if(!directed) G[b].push_back(a); } }

template <typename T>
struct WeightedUnionFind{
    unordered_map<long long, long long> par, rank, siz;
    unordered_map<T, T> diff_weight;
    T e;

    WeightedUnionFind(const T &_e = 0) : e(_e){
    }

    void init(const T &x){
        par[x] = x;
        rank[x] = 0;
        siz[x] = 1;
        diff_weight[x] = e;
    }

    int root(const int &x){
        if(par.find(x) == par.end()){
            init(x);
        }
        if(par[x] == x){
            return x;
        }
        int rx = root(par[x]);
        diff_weight[x] += diff_weight[par[x]];
        return par[x] = rx;
    }

    T weight(const int &x){
        root(x);
        return diff_weight[x];
    }

    T diff(const int &x, const int &y){
        return weight(y) - weight(x);
    }

    void unite(const int &x, const int &y, T w){
        if(par.find(x) == par.end()){
            init(x);
        }
        if(par.find(y) == par.end()){
            init(y);
        }
        w += weight(x);
        w -= weight(y);

        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;

        if(rank[rx] < rank[ry]){
            swap(rx, ry);
            w = -w;
        }

        par[ry] = rx;
        siz[rx] += siz[ry];
        diff_weight[ry] = w;
        if(rank[rx] == rank[ry]) ++rank[rx];
    }

    bool same(const int &x, const int &y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(const int &x){
        return siz[root(x)];
    }
};

template <long long Modulus>
struct ModInt{
    long long val;
    constexpr ModInt(const long long &_val = 0) noexcept : val(_val) {
        normalize();
    }
    void normalize(){
        val = (val % Modulus + Modulus) % Modulus;
    }
    inline ModInt& operator+=(const ModInt& rhs) noexcept {
        if(val += rhs.val, val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt& operator-=(const ModInt& rhs) noexcept {
        if(val -= rhs.val, val < 0) val += Modulus;
        return *this;
    }
    inline ModInt& operator*=(const ModInt& rhs) noexcept {
        val = val * rhs.val % Modulus;
        return *this;
    }
    inline ModInt& operator/=(const ModInt& rhs) noexcept {
        val = val * inv(rhs.val).val % Modulus;
        return *this;
    }
    inline ModInt& operator++() noexcept {
        if(++val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt operator++(int) noexcept {
        ModInt t = val;
        if(++val >= Modulus) val -= Modulus;
        return t;
    }
    inline ModInt& operator--() noexcept {
        if(--val < 0) val += Modulus;
        return *this;
    }
    inline ModInt operator--(int) noexcept {
        ModInt t = val;
        if(--val < 0) val += Modulus;
        return t;
    }
    inline ModInt operator-() const noexcept { return (Modulus - val) % Modulus; }
    inline ModInt inv(void) const { return inv(val); }
    ModInt inv(const long long& n) const {
        long long a = n, b = Modulus, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= Modulus;
        if(u < 0) u += Modulus;
        return u;
    }
    friend inline ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }
    friend inline ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend inline ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend inline ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }
    friend inline bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val == rhs.val; }
    friend inline bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val != rhs.val; }
    friend inline istream& operator>>(istream& is, ModInt& x) noexcept {
        is >> x.val;
        x.normalize();
        return is;
    }
    friend inline ostream& operator<<(ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

namespace modcalc{

    template <typename T>
    T modpow(T x, T n, const T &m){
        T ret = 1 % m;
        x %= m;
        while(n > 0){
            if(n & 1) (ret *= x) %= m;
            (x *= x) %= m;
            n >>= 1;
        }
        return ret;
    }

    template <typename T>
    T modinv(T a, T m){
        T b = m, u = 1, v = 0;
        while(b){
            T t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }

    template <typename T>
    T modarithmeticsum(T a, T d, T n, T m){
        T m2 = m * 2;
        a %= m2, n %= m2, d %= m2;
        T b = (n - 1) * d % m2;
        return ((n * (a * 2 + b) % m2) / 2) % m;
    }

    template <typename T>
    T modgeometricsum(T a, T r, T n, T m){
        a %= m;
        if(r == 1){
            n %= m;
            return a * n % m;
        }
        return a * (modpow(r, n, m) + m - 1) % m * modinv(r - 1, m) % m;
    }

    template <typename T>
    T modgeometricsum2(T a, T r, T n, T m){
        a %= m;
        if(r == 1){
            n %= m;
            return a * n % m;
        }
        T ret = 0;
        T x = 1 % m;
        T sum = 0;
        for(int i = 0; n > 0; ++i){
            if(n & 1){
                (ret += x * modpow(r, sum, m) % m) %= m;
                sum |= 1LL << i;
            }
            (x += x * modpow(r, 1LL << i, m) % m) %= m;
            n >>= 1;
        }
        return a * ret % m;
    }
}

ll n, q;

using mint = ModInt<998244353>;

void input(){
    in(n, q);
}

void solve(){
    WeightedUnionFind<ll> uf;
    ll r = 0, check = 0, ok = n;
    while(q--){
        ll t; in(t);
        if(t == 1){
            ll u, v; in(u, v); u--, v--; u += r, v += r;
            if(!uf.same(u, v)){
                ok--;
            }else if(abs(uf.diff(u, v)) % 2 == 1){
                check = 1;
            }
            uf.unite(u, v, 0);

            if(check){
                out(0);
            }else{
                out(modcalc::modpow(2LL, ok, MOD));
            }
        }else if(t == 2){
            ll u, v; in(u, v); u--, v--; u += r, v += r;
            if(!uf.same(u, v)){
                ok--;
            }else if(abs(uf.diff(u, v)) % 2 == 0){
                check = 1;
            }
            if(u == v) check = 1;
            uf.unite(u, v, 1);

            if(check){
                out(0);
            }else{
                out(modcalc::modpow(2LL, ok, MOD));
            }
        }else{
            r += n;
            check = 0;
            ok = n;
            out(modcalc::modpow(2LL, ok, MOD));
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    
    input();
    solve();
}
0