#866403 (C++17) No.2293 無向辺 2-SAT

• 問題: No.2293 無向辺 2-SAT
• ユーザー: shobonvip
• 提出日時: 2023-05-05 22:06:17
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 500 ms / 4,000 ms
• コード長: 2,894 bytes
• コンパイル時間: 3,944 ms
• コンパイル使用メモリ: 265,980 KB
• 実行使用メモリ: 9,068 KB
• 最終ジャッジ日時: 2024-05-02 16:26:25
• 合計ジャッジ時間: 31,844 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	424 ms; 9,068 KB
testcase_04	AC	405 ms; 5,376 KB
testcase_05	AC	383 ms; 5,376 KB
testcase_06	AC	385 ms; 5,376 KB
testcase_07	AC	277 ms; 5,376 KB
testcase_08	AC	398 ms; 5,376 KB
testcase_09	AC	367 ms; 5,376 KB
testcase_10	AC	365 ms; 5,376 KB
testcase_11	AC	408 ms; 5,376 KB
testcase_12	AC	392 ms; 5,376 KB
testcase_13	AC	378 ms; 5,376 KB
testcase_14	AC	347 ms; 5,376 KB
testcase_15	AC	370 ms; 5,376 KB
testcase_16	AC	388 ms; 5,376 KB
testcase_17	AC	403 ms; 5,376 KB
testcase_18	AC	389 ms; 5,376 KB
testcase_19	AC	200 ms; 5,376 KB
testcase_20	AC	405 ms; 5,376 KB
testcase_21	AC	427 ms; 5,376 KB
testcase_22	AC	416 ms; 5,376 KB
testcase_23	AC	419 ms; 5,376 KB
testcase_24	AC	405 ms; 5,376 KB
testcase_25	AC	500 ms; 5,376 KB
testcase_26	AC	404 ms; 5,376 KB
testcase_27	AC	400 ms; 5,376 KB
testcase_28	AC	396 ms; 5,376 KB
testcase_29	AC	407 ms; 5,376 KB
testcase_30	AC	414 ms; 5,376 KB
testcase_31	AC	396 ms; 5,376 KB
testcase_32	AC	400 ms; 5,376 KB
testcase_33	AC	401 ms; 5,376 KB
testcase_34	AC	398 ms; 5,376 KB
testcase_35	AC	418 ms; 5,376 KB
testcase_36	AC	407 ms; 5,376 KB
testcase_37	AC	395 ms; 5,376 KB
testcase_38	AC	391 ms; 5,376 KB
testcase_39	AC	395 ms; 5,376 KB
testcase_40	AC	388 ms; 5,376 KB
testcase_41	AC	396 ms; 5,376 KB
testcase_42	AC	385 ms; 5,376 KB
testcase_43	AC	393 ms; 5,376 KB
testcase_44	AC	410 ms; 5,376 KB
testcase_45	AC	399 ms; 5,376 KB
testcase_46	AC	394 ms; 5,376 KB
testcase_47	AC	403 ms; 5,376 KB
testcase_48	AC	392 ms; 5,376 KB
testcase_49	AC	416 ms; 5,376 KB
testcase_50	AC	421 ms; 5,376 KB
testcase_51	AC	411 ms; 5,376 KB
testcase_52	AC	411 ms; 5,376 KB
testcase_53	AC	447 ms; 5,376 KB
testcase_54	AC	424 ms; 5,376 KB
testcase_55	AC	423 ms; 5,376 KB

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;

namespace shobon {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
    int _n;
    std::vector<int> parent_or_size;

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        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;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        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;
    }
};

}  // namespace atcoder

typedef modint998244353 mint;
typedef long long ll;

int main(){
	int n, q; cin >> n >> q;
	vector<pair<int,int>> stack;
	shobon::dsu uf(2*n);
	mint ans = mint(2).pow(n);
	mint inv2 = mint(2).inv();
	for (int i=0; i<q; i++){
		int t; cin >> t;
		if (t == 2){
			int x, y; cin >> x >> y;
			x--; y--;
			stack.push_back(pair(x, n+y));
			stack.push_back(pair(y, n+x));
			if (!uf.same(x, n+y)) ans *= inv2;
			uf.merge(x, n+y);
			uf.merge(y, n+x);
			if (uf.same(x, n+x)) ans = 0;
			if (uf.same(y, n+y)) ans = 0;			
		}else if(t == 1){
			int x,y; cin >> x >> y;
			x--; y--;
			stack.push_back(pair(x, y));
			stack.push_back(pair(n+y, n+x));
			if (!uf.same(x, y)) ans *= inv2;
			uf.merge(x, y);
			uf.merge(n+y, n+x);
			if (uf.same(x, n+x)) ans = 0;
			if (uf.same(y, n+y)) ans = 0;	
		}else{
			for (auto [u,v]: stack){
				uf.parent_or_size[u] = -1;
				uf.parent_or_size[v] = -1;
			}
			stack.clear();
			ans = mint(2).pow(n);
		}
		cout << ans.val() << endl;
	}
}