#866821 (C++14) No.2293 無向辺 2-SAT

提出ソース

結果

問題	No.2293 無向辺 2-SAT
ユーザー	laoidn
提出日時	2023-05-06 03:08:49
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,884 bytes
コンパイル時間	4,697 ms
コンパイル使用メモリ	247,324 KB
実行使用メモリ	11,112 KB
最終ジャッジ日時	2024-05-02 20:35:35
合計ジャッジ時間	14,626 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	4 ms 5,716 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	WA	-
testcase_04	AC	599 ms 5,740 KB
testcase_05	AC	472 ms 5,376 KB
testcase_06	AC	717 ms 5,376 KB
testcase_07	TLE	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
ll GCD(ll m, ll n) {
  // ベースケース
  if (n == 0) return m;

  // 再帰呼び出し
  return GCD(n, m % n);
}

ll minlong = 0;

long long Power(long long a, long long b, long long m) {
  long long p = a, Answer = 1;
  for (int i = 0; i < 63; i++) {
    ll wari = (1LL << i);
    if ((b / wari) % 2 == 1) {
      Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
    }
    p = (p * p) % m;
  }
  return Answer;
}

// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
  return (a * Power(b, m - 2, m)) % m;
}

// nCr mod 1000000007 を返す関数
long long nCk(ll n, ll r) {
  const long long M = 1000000007;

  // 手順 1: 分子 a を求める
  long long a = 1;
  for (int i = 1; i <= n; i++) a = (a * i) % M;

  // 手順 2: 分母 b を求める
  long long b = 1;
  for (int i = 1; i <= r; i++) b = (b * i) % M;
  for (int i = 1; i <= n - r; i++) b = (b * i) % M;

  // 手順 3: 答えを求める
  return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// nCk mint を返す関数。
ll modnCk(ll n, ll r) {
  ll a = 1;
  for (ll i = n; i > n - r; i--) {
    a *= i;
    a /= n + 1 - i;
  }
  return a;
}
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[K] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
  Q.push(make_pair(cur[K], K));
  while (!Q.empty()) {
    ll pos = Q.top().second;
    Q.pop();
    if (kaku[pos]) continue;
    kaku[pos] = true;
    for (ll i = 0; i < G[pos].size(); i++) {
      ll nex = G[pos][i].first;
      ll cost = G[pos][i].second;
      if (cur[nex] > cur[pos] + cost) {
        cur[nex] = cur[pos] + cost;
        Q.push(make_pair(cur[nex], nex));
      }
    }
  }
  return cur;
}
ll f(ll x, vll &memo, ll D, vector<pair<ll, ll>> &X) {
  if (memo[x] != -1) return memo[x];
  if (x < D) return 0;
  ll y = x - D;
  ll x1, x2, y1, y2;
  tie(x1, y1) = X[y];
  tie(x2, y2) = X[x];
  ll cost = abs(x1 - x2) + abs(y1 - y2);
  ll res = cost + f(y, memo, D, X);
  return memo[x] = res;
}
template <class T>
struct BIT {
  int n;                  // 要素数
  vector<T> bit[600000];  // データの格納先
  BIT(int n_) { init(n_); }
  void init(int n_) {
    n = n_ + 1;
    for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
  }
  void add_sub(int p, int i, T x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[p][idx] += x;
    }
  }
  void add(int l, int r, T x) {  // [l,r) の区間で加算
    add_sub(0, l, -x * (l - 1));
    add_sub(0, r, x * (r - 1));
    add_sub(1, l, x);
    add_sub(1, r, -x);
  }
  T sum_sub(int p, int i) {
    T s(0);
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[p][idx];
    }
    return s;
  }
  T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
  // sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値)
  T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
  // 任意の区間を計算することが可能これは[l,r)の区間和を計算している。
  int lower_bound(T w) {  // a_1 + a_2 + ... + a_x >= w となるような最小の x
                          // を求める(ただし a_i >= 0)
    if (w <= 0) {
      return 0;
    } else {
      int x = 0, r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0;
           len = len >> 1) {  // 長さlenは1段下るごとに半分に
        if (x + len < n && bit[x + len] < w) {  // 採用するとき
          w -= bit[x + len];
          x += len;
        }
      }
      return x + 1;
    }
  }
};
vll BFS(vvll &G, ll &x) {
  vll cut(G.size(), INF);
  queue<ll> Q;
  Q.push(x);
  cut[x] = 0;
  while (!Q.empty()) {
    ll a = Q.front();
    Q.pop();
    rep(i, G[a].size()) {
      if (cut[G[a][i]] > cut[a] + 1) {
        cut[G[a][i]] = cut[a] + 1;
        Q.push(G[a][i]);
      }
    }
  }
  return cut;
}
template <class Abel>
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;
  vector<int> siz;
  UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); }

  void init(int n = 1, Abel SUM_UNITY = 0) {
    par.resize(n);
    rank.resize(n);
    diff_weight.resize(n);
    siz.resize(n);
    for (int i = 0; i < n; ++i)
      par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      diff_weight[x] +=
          diff_weight[par[x]];  // 累積和をとることで重みがつけられる。
      return par[x] = r;
    }
  }

  Abel weight(int x) {
    root(x);                // 経路圧縮
    return diff_weight[x];  // 重みを返す
  }

  bool issame(int x, int y) {
    return root(x) == root(y);  // 通常時も同じ
  }

  // weight(y) - weight(x) = w となるように merge する
  bool merge(int x, int y, Abel w) {
    // x と y それぞれについて、 root との重み差分を補正
    w += weight(x);
    w -= weight(y);
    // x と y の root へ (x と y が既につながっていたら false を返すようにした)
    x = root(x);
    y = root(y);
    if (x == y) return false;

    // rank[x] >= rank[y] となるように x と y を swap (それに合わせて w
    // も符号反転します)これはUnion by
    // rankと呼ばれ根の高さをO(logN)で抑えられる手法である。
    if (rank[x] < rank[y]) swap(x, y), w = -w;

    // y (のroot) を x (のroot)
    // の下にくっつける(高さが低い方の根付き木を高いほうに併合する)
    if (rank[x] == rank[y]) ++rank[x];
    siz[x] += siz[y];
    par[y] = x;

    // x が y の親になるので、x と y の差分を diff_weight[y] に記録
    diff_weight[y] = w;
    return true;
  }
  Abel diff(int x, int y) { return weight(y) - weight(x); }
  int size(int x) { return siz[root(x)]; }
};

void Yes(bool b) {
  if (b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
vector<long long> yaku(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());  // 昇順に並べる
  return ret;
}
// #include <atcoder/lazysegtree>用
using S = long long;
using F = long long;

S op(S a, S b) { return std::max(a, b); }
S e() { return -INF; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
ll N, M, K, XP = 0;
vll cur;
vll A;
void dfs(ll now, ll past, vvll G) {
  A[now] = true;
  rep(i, G[now].size()) {
    if (G[now][i] != past && !A[G[now][i]]) {
      dfs(G[now][i], now, G);
    }
  }
  cur[now] = XP;
  XP++;
}
int GetRandom(int min, int max) {
  return min + (rand() * (max - min) / (RAND_MAX));
}

int main() {
  cout << fixed << setprecision(20);
  ll N, M, K, L, count;
  cin >> N >> M;
  count = Power(2, N, 998244353);
  modint998244353 ans = count;
  dsu d(N), d1(N);
  rep(i, M) {
    ll a, b, c;
    cin >> c;

    if (c == 1) {
      cin >> a >> b;
      --a, --b;
      if (d1.same(a, b) && a != b) ans = 0;
      d.merge(a, b);


      if(a!=b)ans /= 2;
      
    }
    else if (c == 2) {
      cin >> a >> b;
      --a, --b;
      if (d.same(a, b) || a == b) ans = 0;
      d1.merge(a, b);
      ans /= 2;
    } else {
      dsu x(N);
      d = x;
      d1 = x;
      ans = count;
    }
    cout << ans.val() << endl;
  }
}

yukicoder

結果

テストケース

ソースコード