結果

問題 No.2294 Union Path Query (Easy)
ユーザー DaylightDaylight
提出日時 2023-05-06 13:17:46
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 1,814 ms / 4,000 ms
コード長 16,805 bytes
コンパイル時間 4,239 ms
コンパイル使用メモリ 232,060 KB
実行使用メモリ 391,312 KB
最終ジャッジ日時 2023-09-04 20:19:41
合計ジャッジ時間 72,964 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1,814 ms
389,016 KB
testcase_04 AC 1,206 ms
257,480 KB
testcase_05 AC 1,085 ms
235,492 KB
testcase_06 AC 1,573 ms
390,852 KB
testcase_07 AC 1,570 ms
391,312 KB
testcase_08 AC 1,741 ms
385,380 KB
testcase_09 AC 1,737 ms
385,504 KB
testcase_10 AC 1,495 ms
390,928 KB
testcase_11 AC 1,502 ms
390,996 KB
testcase_12 AC 1,501 ms
390,692 KB
testcase_13 AC 1,636 ms
387,052 KB
testcase_14 AC 1,373 ms
389,068 KB
testcase_15 AC 1,371 ms
391,248 KB
testcase_16 AC 1,379 ms
388,188 KB
testcase_17 AC 1,414 ms
385,276 KB
testcase_18 AC 1,423 ms
388,132 KB
testcase_19 AC 1,404 ms
388,248 KB
testcase_20 AC 1,389 ms
388,528 KB
testcase_21 AC 1,399 ms
389,240 KB
testcase_22 AC 1,554 ms
383,712 KB
testcase_23 AC 1,407 ms
388,104 KB
testcase_24 AC 1,402 ms
389,220 KB
testcase_25 AC 1 ms
4,384 KB
testcase_26 AC 2 ms
4,384 KB
testcase_27 AC 2 ms
4,384 KB
testcase_28 AC 669 ms
36,384 KB
testcase_29 AC 732 ms
73,712 KB
testcase_30 AC 777 ms
98,720 KB
testcase_31 AC 828 ms
123,876 KB
testcase_32 AC 877 ms
125,512 KB
testcase_33 AC 920 ms
144,440 KB
testcase_34 AC 976 ms
174,060 KB
testcase_35 AC 1,017 ms
204,660 KB
testcase_36 AC 1,063 ms
220,436 KB
testcase_37 AC 1,093 ms
234,980 KB
testcase_38 AC 1,173 ms
250,628 KB
testcase_39 AC 1,245 ms
263,188 KB
testcase_40 AC 1,302 ms
263,504 KB
testcase_41 AC 1,345 ms
263,652 KB
testcase_42 AC 1,389 ms
276,920 KB
testcase_43 AC 1,442 ms
306,460 KB
testcase_44 AC 1,488 ms
336,724 KB
testcase_45 AC 1,548 ms
333,868 KB
testcase_46 AC 1,620 ms
363,644 KB
testcase_47 AC 1,642 ms
388,824 KB
testcase_48 AC 1,354 ms
388,980 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 PotentialUnionFind(S, alias op, alias e, alias inv) {
    import std;

private:
    static if (is(typeof(e) : string)) {
        auto unit() {
            return mixin(e);
        }
    } else {
        alias unit = e;
    }
    int treeCnt;
    int[] p;
    S[] potential;
    int N;
public:
    this(int size) {
        N = size;
        p = new int[](N);
        p[] = -1;
        potential = new S[](N);
        potential[] = unit();
        treeCnt = N;
    }

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

    int merge(int x, int y, S w) {
        w = binaryFun!(op)(w, getPotential(x));
        w = binaryFun!(op)(w, unaryFun!(inv)(getPotential(y)));
        return link(leader(x), leader(y), w);
    }

private:
    int link(int x, int y, S w) {
        if (x == y)
            return x;
        if (p[x] > p[y]) {
            swap(x, y);
            w = unaryFun!(inv)(w);
        }
        p[x] += p[y];
        p[y] = x;
        treeCnt--;
        potential[y] = w;
        return x;
    }

public:
    int leader(int x) {
        if (p[x] < 0) {
            return x;
        } else {
            int l = leader(p[x]);
            potential[x] = binaryFun!(op)(potential[x], potential[p[x]]);
            return p[x] = l;
        }
    }

    S getPotential(int x) {
        leader(x);
        return potential[x];
    }

    S diff(int x, int y) {
        return binaryFun!(op)(getPotential(y), unaryFun!(inv)(getPotential(x)));
    }

    int countTree() {
        return treeCnt;
    }

    int size(int a) {
        return -p[leader(a)];
    }
}


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, X, Q;
    cin(N, X, Q);
    auto dsu = new PotentialUnionFind!(int, "a^b", "0", "a")(N);
    auto B = new long[][][](N, 30, 2);
    foreach (ref v; B) {
        foreach (ref vv; v) {
            vv[0] = 1;
        }
    }
    foreach (_; 0 .. Q) {
        int k;
        cin(k);
        if (k == 1) {
            int u, w;
            cin(u, w);
            int a = dsu.leader(u);
            int b = dsu.leader(X);
            int c = dsu.merge(u, X, w);
            w = dsu.diff(a, b);
            if (a != c)
                swap(a, b);
            foreach (d; 0 .. 30) {
                B[a][d][0] += B[b][d][w >> d & 1];
                B[a][d][1] += B[b][d][1 - (w >> d & 1)];
            }
        } else if (k == 2) {
            int u, v;
            cin(u, v);
            if (dsu.same(u, v)) {
                int d = dsu.diff(u, v);
                d.writeln;
                X += d;
                X %= N;
            } else {
                (-1).writeln;
            }
        } else if (k == 3) {
            int v;
            cin(v);
            v = dsu.leader(v);
            mint ans = 0;
            foreach (d; 0 .. 30) {
                ans += (mint(2) ^^ d) * B[v][d][0] * B[v][d][1];
            }
            ans.val.writeln;
        } else if (k == 4) {
            int v;
            cin(v);
            X += v;
            X %= N;
        }
    }
}
0