#866882 (D) No.2293 無向辺 2-SAT

提出ソース

結果

問題	No.2293 無向辺 2-SAT
ユーザー	Daylight
提出日時	2023-05-06 11:03:06
言語	D (dmd 2.106.1)
結果	AC
実行時間	405 ms / 4,000 ms
コード長	16,091 bytes
コンパイル時間	4,747 ms
コンパイル使用メモリ	237,456 KB
実行使用メモリ	37,560 KB
最終ジャッジ日時	2024-06-22 17:51:53
合計ジャッジ時間	32,170 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	5 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	405 ms 37,560 KB
testcase_04	AC	385 ms 6,940 KB
testcase_05	AC	355 ms 6,944 KB
testcase_06	AC	352 ms 6,944 KB
testcase_07	AC	192 ms 12,656 KB
testcase_08	AC	375 ms 6,940 KB
testcase_09	AC	324 ms 6,940 KB
testcase_10	AC	325 ms 6,940 KB
testcase_11	AC	401 ms 6,940 KB
testcase_12	AC	372 ms 6,940 KB
testcase_13	AC	315 ms 6,940 KB
testcase_14	AC	296 ms 6,944 KB
testcase_15	AC	288 ms 6,940 KB
testcase_16	AC	384 ms 6,940 KB
testcase_17	AC	398 ms 13,744 KB
testcase_18	AC	383 ms 6,940 KB
testcase_19	AC	178 ms 6,944 KB
testcase_20	AC	368 ms 6,940 KB
testcase_21	AC	358 ms 6,944 KB
testcase_22	AC	381 ms 13,340 KB
testcase_23	AC	387 ms 12,732 KB
testcase_24	AC	382 ms 13,608 KB
testcase_25	AC	388 ms 13,580 KB
testcase_26	AC	385 ms 14,132 KB
testcase_27	AC	383 ms 13,820 KB
testcase_28	AC	385 ms 12,696 KB
testcase_29	AC	387 ms 13,700 KB
testcase_30	AC	390 ms 13,632 KB
testcase_31	AC	384 ms 13,864 KB
testcase_32	AC	318 ms 6,940 KB
testcase_33	AC	320 ms 6,940 KB
testcase_34	AC	316 ms 6,940 KB
testcase_35	AC	318 ms 6,944 KB
testcase_36	AC	320 ms 6,944 KB
testcase_37	AC	319 ms 6,940 KB
testcase_38	AC	319 ms 6,940 KB
testcase_39	AC	319 ms 6,940 KB
testcase_40	AC	319 ms 6,944 KB
testcase_41	AC	272 ms 6,944 KB
testcase_42	AC	290 ms 6,940 KB
testcase_43	AC	312 ms 6,944 KB
testcase_44	AC	334 ms 6,944 KB
testcase_45	AC	346 ms 6,944 KB
testcase_46	AC	354 ms 6,944 KB
testcase_47	AC	351 ms 6,940 KB
testcase_48	AC	362 ms 6,944 KB
testcase_49	AC	376 ms 6,944 KB
testcase_50	AC	373 ms 6,944 KB
testcase_51	AC	391 ms 6,940 KB
testcase_52	AC	391 ms 14,388 KB
testcase_53	AC	381 ms 12,744 KB
testcase_54	AC	388 ms 12,532 KB
testcase_55	AC	397 ms 13,204 KB

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

ソースコード

raw source code

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;
        }
    }
}

yukicoder

結果

テストケース

ソースコード