結果

問題 No.3695 同室と別室
コンテスト
ユーザー yuki2006
提出日時 2026-08-26 23:52:20
言語 JavaScript
(node v26.7.0 + ACL)
コンパイル:
true
実行:
node _filename_ ONLINE_JUDGE
結果
AC  
実行時間 121 ms / 2,000 ms
+ 760µs
コード長 1,208 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3 ms
コンパイル使用メモリ 6,528 KB
実行使用メモリ 100,260 KB
最終ジャッジ日時 2026-09-09 20:50:46
合計ジャッジ時間 2,124 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

const MOD = 998244353n;
const d = require('fs').readFileSync(0, 'utf8').split(/\s+/);
let p = 0;
const n = +d[p++], q = +d[p++];
const par = new Int32Array(n + 1), rnk = new Int32Array(n + 1), w = new Int8Array(n + 1);
for (let i = 0; i <= n; i++) par[i] = i;
const stack = new Int32Array(n + 1);
function find(x) {
  let top = 0;
  while (par[x] !== x) { stack[top++] = x; x = par[x]; }
  const root = x;
  for (let i = top - 1; i >= 0; i--) { const v = stack[i]; w[v] ^= w[par[v]]; par[v] = root; }
  return root;
}
let ok = true;
for (let i = 0; i < q; i++) {
  const t = +d[p++], a = +d[p++], b = +d[p++];
  const ra = find(a), rb = find(b);
  if (ra === rb) {
    if (((w[a] ^ w[b]) & 1) !== t) ok = false;
  } else {
    let x = ra, y = rb, wx = w[a], wy = w[b];
    if (rnk[ra] < rnk[rb]) { x = rb; y = ra; wx = w[b]; wy = w[a]; }
    par[y] = x;
    w[y] = (wx ^ wy ^ t) & 1;
    if (rnk[x] === rnk[y]) rnk[x]++;
  }
}
if (!ok) { console.log(0); } else {
  let comp = 0;
  for (let i = 1; i <= n; i++) if (find(i) === i) comp++;
  let ans = 1n, base = 2n, e = BigInt(comp);
  while (e > 0n) { if (e & 1n) ans = ans * base % MOD; base = base * base % MOD; e >>= 1n; }
  console.log(ans.toString());
}
0