結果

問題 No.2293 無向辺 2-SAT
ユーザー DaylightDaylight
提出日時 2023-05-06 11:03:06
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 416 ms / 4,000 ms
コード長 16,091 bytes
コンパイル時間 6,029 ms
コンパイル使用メモリ 232,288 KB
実行使用メモリ 38,640 KB
最終ジャッジ日時 2023-09-04 20:17:12
合計ジャッジ時間 36,132 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 3 ms
4,928 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 416 ms
38,640 KB
testcase_04 AC 383 ms
5,932 KB
testcase_05 AC 362 ms
5,208 KB
testcase_06 AC 357 ms
5,264 KB
testcase_07 AC 193 ms
8,000 KB
testcase_08 AC 370 ms
6,044 KB
testcase_09 AC 323 ms
5,980 KB
testcase_10 AC 328 ms
5,984 KB
testcase_11 AC 385 ms
5,968 KB
testcase_12 AC 374 ms
6,056 KB
testcase_13 AC 325 ms
4,588 KB
testcase_14 AC 308 ms
4,548 KB
testcase_15 AC 294 ms
4,380 KB
testcase_16 AC 377 ms
6,976 KB
testcase_17 AC 391 ms
14,244 KB
testcase_18 AC 375 ms
6,056 KB
testcase_19 AC 178 ms
5,220 KB
testcase_20 AC 366 ms
6,712 KB
testcase_21 AC 358 ms
6,012 KB
testcase_22 AC 377 ms
13,412 KB
testcase_23 AC 380 ms
13,424 KB
testcase_24 AC 378 ms
13,980 KB
testcase_25 AC 385 ms
14,280 KB
testcase_26 AC 385 ms
14,504 KB
testcase_27 AC 381 ms
14,924 KB
testcase_28 AC 384 ms
13,456 KB
testcase_29 AC 385 ms
13,424 KB
testcase_30 AC 388 ms
13,460 KB
testcase_31 AC 387 ms
13,452 KB
testcase_32 AC 330 ms
6,004 KB
testcase_33 AC 324 ms
7,036 KB
testcase_34 AC 326 ms
6,764 KB
testcase_35 AC 329 ms
7,576 KB
testcase_36 AC 324 ms
7,244 KB
testcase_37 AC 326 ms
6,044 KB
testcase_38 AC 328 ms
5,972 KB
testcase_39 AC 325 ms
6,040 KB
testcase_40 AC 328 ms
6,000 KB
testcase_41 AC 280 ms
6,500 KB
testcase_42 AC 301 ms
5,988 KB
testcase_43 AC 320 ms
5,996 KB
testcase_44 AC 332 ms
6,724 KB
testcase_45 AC 347 ms
7,024 KB
testcase_46 AC 356 ms
5,980 KB
testcase_47 AC 369 ms
6,004 KB
testcase_48 AC 363 ms
5,964 KB
testcase_49 AC 364 ms
7,208 KB
testcase_50 AC 373 ms
6,788 KB
testcase_51 AC 375 ms
7,256 KB
testcase_52 AC 379 ms
13,376 KB
testcase_53 AC 381 ms
14,760 KB
testcase_54 AC 390 ms
13,988 KB
testcase_55 AC 390 ms
13,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

public import std;

DList!string scan_buffer;
DList!char char_buffer;
static this() {
    scan_buffer = DList!(string)();
    char_buffer = DList!(char)();
}

void cin()() {

}

void cin(T, A...)(ref T a, ref A tail) {
    import std.traits : isArray;

    static if (typeof(a).stringof == "string") {
        if (!char_buffer.empty) {
            a = char_buffer.array.map!(x => x.to!string).join();
            char_buffer.clear();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token;
        }
    } else static if (typeof(a).stringof == "char") {
        if (!char_buffer.empty) {
            a = char_buffer.front();
            char_buffer.removeFront();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token[0];
            if (token.length > 1) {
                foreach (c; token[1 .. $]) {
                    char_buffer.insertBack(c);
                }
            }
        }
    } else static if (typeof(a).stringof == "char[]") {
        if (a.length == 0) {
            string token;
            cin(token);
            foreach (c; token) {
                a ~= c;
            }
        } else {
            foreach (ref v; a) {
                cin(v);
            }
        }
    } else static if (isArray!(typeof(a))) {
        foreach (ref v; a) {
            cin(v);
        }
    } else static if (isTuple!(typeof(a))) {
        foreach (i, _; a) {
            cin(a[i]);
        }
    } else {
        if (!char_buffer.empty) {
            writeln(char_buffer.array.map!(x => x.to!string));
            a = char_buffer.array.map!(x => x.to!string).join().to!T;
            char_buffer.clear();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token.to!T;
        }
    }
    cin(tail);
}

bool chmin(T)(ref T a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

bool chmax(T)(ref T a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

alias PQueue(T = long, alias less = "a<b") = BinaryHeap!(Array!T, less);
class RollbackUnionFind {
    import std;

private:
    int N;
    int[] p;
    alias P = Tuple!(int, int);
    DList!P history;
public:
    this(int size) {
        N = size;
        p = new int[](size);
        p.fill(-1);
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    void merge(int x, int y) {
        link(leader(x), leader(y));
    }

    void link(int x, int y) {
        if (x == y)
            return;
        if (p[x] > p[y])
            swap(x, y);
        if (p[x] == p[y]) {
            history.insertBack(P(x, p[x]));
            p[x]--;
        }
        history.insertBack(P(y, p[y]));
        p[y] = x;
    }

    int leader(int x) {
        if (p[x] < 0)
            return x;
        else
            return leader(p[x]);
    }

    void snapshot() {
        history.clear();
    }

    void rollback() {
        while (!history.empty()) {
            auto pa = history.back();
            history.removeBack();
            p[pa[0]] = pa[1];
        }
    }
}


import std.typecons : Tuple;

ulong safeMod(long x, long m) @safe pure nothrow @nogc
{
    x %= m;
    if (x < 0)
        x += m;
    return x;
}

ulong[2] umul128(ulong a, ulong b) @safe @nogc pure nothrow
{
    immutable ulong au = a >> 32;
    immutable ulong bu = b >> 32;
    immutable ulong al = a & ((1UL << 32) - 1);
    immutable ulong bl = b & ((1UL << 32) - 1);

    ulong t = al * bl;
    immutable ulong w3 = t & ((1UL << 32) - 1);
    ulong k = t >> 32;
    t = au * bl + k;

    k = t & ((1UL << 32) - 1);
    immutable ulong w1 = t >> 32;
    t = al * bu + k;
    k = t >> 32;
    return [au * bu + w1 + k, t << 32 + w3];
}

struct Barrett
{
    uint _m;
    ulong im;
    this(uint m) @safe @nogc pure nothrow
    {
        _m = m;
        im = (cast(ulong)(-1)) / m + 1;
    }

    uint umod() @safe @nogc pure nothrow
    {
        return _m;
    }

    uint mul(uint a, uint b) @safe @nogc pure nothrow
    {
        ulong z = a;
        z *= b;
        immutable ulong x = umul128(z, im)[0];
        uint v = cast(uint)(z - x * _m);
        if (_m <= v)
            v += _m;
        return v;
    }
}

long ctPowMod(long x, long n, int m) @safe pure nothrow @nogc
{
    if (m == 1)
        return 0;
    uint _m = cast(uint) m;
    ulong r = 1;
    ulong y = safeMod(x, m);
    while (n)
    {
        if (n & 1)
            r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

bool ctIsPrime(int n) @safe pure nothrow @nogc
{
    if (n <= 1)
        return false;
    if (n == 2 || n == 7 || n == 61)
        return true;
    if (n % 2 == 0)
        return false;
    long d = n - 1;
    while (d % 2 == 0)
        d /= 2;
    foreach (a; [2, 7, 61])
    {
        long t = d;
        long y = ctPowMod(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1)
        {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0)
        {
            return false;
        }
    }
    return true;
}

enum bool isPrime(int n) = ctIsPrime(n);

Tuple!(long, long) invGcd(long a, long b) @safe pure nothrow @nogc
{
    a = safeMod(a, b);
    if (a == 0)
        return Tuple!(long, long)(b, 0);
    long s = b, t = a, m0 = 0, m1 = 1;
    while (t)
    {
        immutable long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        long tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0)
        m0 += b / s;
    return Tuple!(long, long)(s, m0);
}

int ctPrimitiveRoot(int m) @safe pure nothrow @nogc
{
    if (m == 2)
        return 1;
    if (m == 167_772_161)
        return 3;
    if (m == 469_762_049)
        return 3;
    if (m == 754_974_721)
        return 11;
    if (m == 998_244_353)
        return 3;
    int[20] divs;
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0)
        x /= 2;
    for (int i = 3; (cast(long) i) * i <= x; i += 2)
        if (x % i == 0)
        {
            divs[cnt++] = i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        divs[cnt++] = x;
    for (int g = 2;; g++)
    {
        bool ok = true;
        foreach (i; 0 .. cnt)
            if (ctPowMod(g, (m - 1) / divs[i], m) == 1)
            {
                ok = false;
                break;
            }
        if (ok)
            return g;
    }
}

enum primitiveRoot(int m) = ctPrimitiveRoot(m);

struct StaticModInt(int m) if (1 <= m) {
    import std.traits : isSigned, isUnsigned, isSomeChar;

    alias mint = StaticModInt;
public:
    static int mod() {
        return m;
    }

    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    this(T)(T v) if (isSigned!T) {
        long x = cast(long)(v % cast(long)(umod()));
        if (x < 0)
            x += umod();
        _v = cast(uint)(x);
    }

    this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
        _v = cast(uint)(v % umod());
    }

    this(bool v) {
        _v = cast(uint)(v) % umod();
    }

    auto opAssign(T)(T v)
            if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
        return this = mint(v);
    }

    inout uint val() pure {
        return _v;
    }

    ref mint opUnary(string op)() pure nothrow @safe if (op == "++") {
        _v++;
        if (_v == umod())
            _v = 0;
        return this;
    }

    ref mint opUnary(string op)() pure nothrow @safe if (op == "--") {
        if (_v == 0)
            _v = umod();
        _v--;
        return this;
    }

    mint opUnary(string op)() if (op == "+" || op == "-") {
        mint x;
        return mixin("x " ~ op ~ " this");
    }

    ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
        mint y = value;
        return opOpAssign!(op)(y);
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
        _v += value._v;
        if (_v >= umod())
            _v -= umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
        _v -= value._v;
        if (_v >= umod())
            _v += umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
        ulong z = _v;
        z *= value._v;
        _v = cast(uint)(z % umod());
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
        return this = this * value.inv();
    }

    ref mint opOpAssign(string op, T)(T value)
            if (op == "^^" && (is(T == int) || is(T == long))) {
        return this = this.pow(value);
    }

    mint pow(long n) const pure {
        assert(0 <= n);
        mint x = this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    mint inv() const pure {
        static if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = invGcd(_v, mod());
            assert(eg[0] == 1);
            return mint(eg[1]);
        }
    }

    mint opBinary(string op, R)(const R value) const pure
    if (op == "+" || op == "-" || op == "*" || op == "/") {
        static if (is(R == mint)) {
            mint x;
            x += this;
            return x.opOpAssign!(op)(value);
        } else {
            mint x;
            x += this;
            mint y = value;
            return x.opOpAssign!(op)(y);
        }
    }

    mint opBinary(string op, R)(const R value) const pure
    if (op == "^^") {
        return pow(value);
    }

    mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
        mint y = value;
        return y.opBinary!(op)(this);
    }

    bool opEquals(R)(const R value) const {
        static if (is(R == mint)) {
            return _v == value._v;
        } else {
            mint y = mint(value);
            return this == y;
        }
    }

private:
    uint _v;
    uint umod() pure const {
        return m;
    }

    enum bool prime = isPrime!(m);
}

struct DynamicModInt(int id) {
    import std.traits : isSigned, isUnsigned, isSomeChar;

    alias mint = DynamicModInt;
public:
    static int mod() {
        return bt.umod();
    }

    static void setMod(int m) {
        assert(1 <= m);
        bt = Barrett(m);
    }

    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    this(T)(T v) if (isSigned!T) {
        long x = cast(long)(v % cast(long)(umod()));
        if (x < 0)
            x += umod();
        _v = cast(uint)(x);
    }

    this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
        _v = cast(uint)(v % umod());
    }

    this(bool v) {
        _v = cast(uint)(v) % umod();
    }

    auto opAssign(T)(T v)
            if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
        return this = mint(v);
    }

    inout uint val() {
        return _v;
    }

    ref mint opUnary(string op)() nothrow @safe if (op == "++") {
        _v++;
        if (_v == umod())
            _v = 0;
        return this;
    }

    ref mint opUnary(string op)() nothrow @safe if (op == "--") {
        if (_v == 0)
            _v = umod();
        _v--;
        return this;
    }

    mint opUnary(string op)() if (op == "+" || op == "-") {
        mint x;
        return mixin("x " ~ op ~ " this");
    }

    ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
        mint y = value;
        return opOpAssign!(op)(y);
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
        _v += value._v;
        if (_v >= umod())
            _v -= umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
        _v -= value._v;
        if (_v >= umod())
            _v += umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
        _v = bt.mul(_v, value._v);
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
        return this = this * value.inv();
    }

    ref mint opOpAssign(string op, T)(T value)
            if (op == "^^" && (is(T == int) || is(T == long))) {
        return this = this.pow(value);
    }

    mint pow(long n) const {
        assert(0 <= n);
        mint x = this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    mint inv() const {
        auto eg = invGcd(_v, mod());
        assert(eg[0] == 1);
        return mint(eg[1]);
    }

    mint opBinary(string op, R)(const R value)
            if (op == "+" || op == "-" || op == "*" || op == "/") {
        static if (is(R == mint)) {
            mint x;
            x += this;
            return x.opOpAssign!(op)(value);
        } else {
            mint y = value;
            return opOpAssign!(op)(y);
        }
    }

    mint opBinary(string op, R)(const R value) const
    if (op == "^^") {
        return pow(value);
    }

    mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
        mint y = value;
        return y.opBinary!(op)(this);
    }

    bool opEquals(R)(const R value) const {
        static if (is(R == mint)) {
            return _v == value._v;
        } else {
            mint y = mint(value);
            return this == y;
        }
    }

private:
    uint _v;
    static Barrett bt = Barrett(998_244_353);
    uint umod() {
        return bt.umod();
    }
}

alias modint998244353 = StaticModInt!(998244353);
alias modint1000000007 = StaticModInt!(1000000007);
alias modint = DynamicModInt!(-1);

alias mint = modint998244353;

void main() {
    int N, Q;
    cin(N, Q);
    auto dsu = new RollbackUnionFind(N * 2);
    int cnt = N;
    bool zero = false;
    foreach (q; 0 .. Q) {
        int k;
        cin(k);
        if (k == 1) {
            int u, v;
            cin(u, v);
            u--;
            v--;
            if (!dsu.same(u, v)) {
                dsu.merge(u, v);
                dsu.merge(u + N, v + N);
                cnt--;
            }
            if (dsu.same(u, u + N)) {
                zero = true;
            }
            if (zero) {
                0.writeln;
            } else {
                (mint(2) ^^ cnt).val.writeln;
            }
        } else if (k == 2) {
            int u, v;
            cin(u, v);
            u--;
            v--;
            if (!dsu.same(u, v + N)) {
                dsu.merge(u, v + N);
                dsu.merge(u + N, v);
                cnt--;
            }
            if (dsu.same(u, u + N)) {
                zero = true;
            }
            if (zero) {
                0.writeln;
            } else {
                (mint(2) ^^ cnt).val.writeln;
            }
        } else {
            zero = false;
            cnt = N;
            dsu.rollback();
            (mint(2) ^^ cnt).val.writeln;
        }
    }
}
0