#1175580 (D) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:40:35
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 509 ms / 3,000 ms
• コード長: 11,881 bytes
• コンパイル時間: 324 ms
• コンパイル使用メモリ: 56,888 KB
• 実行使用メモリ: 22,528 KB
• 最終ジャッジ日時: 2026-09-04 22:12:32
• 合計ジャッジ時間: 8,943 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 30

ソースコード

import core.stdc.stdio : fread, fwrite, stdin, stdout;
import std.array : Appender, appender;

enum MAX_AB = 300;

// 10^9進数で20桁保持する。
// 10進数では最大180桁まで扱える。
enum uint BASE = 1_000_000_000U;
enum LIMB_COUNT = 20;

struct FastScanner
{
private:
    ubyte[1 << 16] buffer;
    size_t position;
    size_t length;

    int readByte()
    {
        if (position >= length)
        {
            length = fread(
                buffer.ptr,
                1,
                buffer.length,
                stdin
            );

            position = 0;

            if (length == 0)
            {
                return -1;
            }
        }

        return buffer[position++];
    }

public:
    int nextInt()
    {
        int c;

        do
        {
            c = readByte();
        }
        while (c <= ' ' && c != -1);

        int sign = 1;

        if (c == '-')
        {
            sign = -1;
            c = readByte();
        }

        int value = 0;

        while ('0' <= c && c <= '9')
        {
            value = value * 10 + c - '0';
            c = readByte();
        }

        return value * sign;
    }
}

struct FixedInt
{
    // 下位桁から格納する。
    uint[LIMB_COUNT] digit;

    static FixedInt one()
    {
        FixedInt result;
        result.digit[0] = 1;
        return result;
    }

    int compare(ref const(FixedInt) other) const
    {
        for (int i = LIMB_COUNT - 1; i >= 0; --i)
        {
            if (digit[i] < other.digit[i])
            {
                return -1;
            }

            if (digit[i] > other.digit[i])
            {
                return 1;
            }
        }

        return 0;
    }

    void addAssign(ref const(FixedInt) other)
    {
        ulong carry = 0;

        foreach (i; 0 .. LIMB_COUNT)
        {
            ulong value =
                cast(ulong)digit[i] + other.digit[i] + carry;

            if (value >= BASE)
            {
                value -= BASE;
                carry = 1;
            }
            else
            {
                carry = 0;
            }

            digit[i] = cast(uint)value;
        }
    }

    void multiplySmall(uint multiplier)
    {
        ulong carry = 0;

        foreach (i; 0 .. LIMB_COUNT)
        {
            ulong value =
                cast(ulong)digit[i] * multiplier + carry;

            digit[i] = cast(uint)(value % BASE);
            carry = value / BASE;
        }
    }

    uint divideSmall(uint divisor)
    {
        ulong remainder = 0;

        for (int i = LIMB_COUNT - 1; i >= 0; --i)
        {
            ulong value =
                remainder * BASE + digit[i];

            digit[i] = cast(uint)(value / divisor);
            remainder = value % divisor;
        }

        return cast(uint)remainder;
    }

    uint modulusSmall(uint divisor) const
    {
        ulong remainder = 0;

        for (int i = LIMB_COUNT - 1; i >= 0; --i)
        {
            remainder =
                (remainder * BASE + digit[i]) % divisor;
        }

        return cast(uint)remainder;
    }
}

struct RawEdge
{
    int u;
    int v;
    int numerator;
    int denominator;
}

struct Edge
{
    int to;
    FixedInt weight;
}

struct PrimePower
{
    int prime;
    int exponent;
}

// 頂点番号だけを保持するindexed heap。
// 同じ頂点がヒープ内に複数回入らない。
struct MinHeap
{
private:
    int[] heap;
    int[] position;
    FixedInt[] distance;
    size_t heapLength;

    bool less(int lhs, int rhs)
    {
        int comparison =
            distance[lhs].compare(distance[rhs]);

        if (comparison != 0)
        {
            return comparison < 0;
        }

        return lhs < rhs;
    }

    void siftUp(int index)
    {
        int vertex = heap[index];

        while (index > 0)
        {
            int parent = (index - 1) / 2;
            int parentVertex = heap[parent];

            if (!less(vertex, parentVertex))
            {
                break;
            }

            heap[index] = parentVertex;
            position[parentVertex] = index;
            index = parent;
        }

        heap[index] = vertex;
        position[vertex] = index;
    }

    void siftDown(int index)
    {
        int vertex = heap[index];

        while (true)
        {
            int left = index * 2 + 1;

            if (cast(size_t)left >= heapLength)
            {
                break;
            }

            int right = left + 1;
            int child = left;

            if (cast(size_t)right < heapLength &&
                less(heap[right], heap[left]))
            {
                child = right;
            }

            int childVertex = heap[child];

            if (!less(childVertex, vertex))
            {
                break;
            }

            heap[index] = childVertex;
            position[childVertex] = index;
            index = child;
        }

        heap[index] = vertex;
        position[vertex] = index;
    }

public:
    this(size_t capacity, FixedInt[] distance)
    {
        heap = new int[capacity];
        position = new int[capacity];
        position[] = -1;

        this.distance = distance;
        heapLength = 0;
    }

    @property bool empty()
    {
        return heapLength == 0;
    }

    void pushOrDecrease(int vertex)
    {
        int index = position[vertex];

        if (index < 0)
        {
            index = cast(int)heapLength;
            heap[heapLength] = vertex;
            position[vertex] = index;
            ++heapLength;
        }

        // distance[vertex]は小さくなるだけなので、
        // 上方向への調整だけでよい。
        siftUp(index);
    }

    int pop()
    {
        int result = heap[0];

        --heapLength;
        position[result] = -1;

        if (heapLength != 0)
        {
            int last = heap[heapLength];

            heap[0] = last;
            position[last] = 0;

            siftDown(0);
        }

        return result;
    }
}

void appendUnsigned(
    ref Appender!string output,
    uint value
)
{
    char[10] buffer;
    int length = 0;

    do
    {
        buffer[length++] =
            cast(char)('0' + value % 10);

        value /= 10;
    }
    while (value != 0);

    for (int i = length - 1; i >= 0; --i)
    {
        output.put(buffer[i]);
    }
}

void appendPaddedNine(
    ref Appender!string output,
    uint value
)
{
    char[9] buffer;

    for (int i = 8; i >= 0; --i)
    {
        buffer[i] =
            cast(char)('0' + value % 10);

        value /= 10;
    }

    output.put(buffer[]);
}

void appendFixedInt(
    ref Appender!string output,
    ref const(FixedInt) value
)
{
    int highest = LIMB_COUNT - 1;

    while (highest > 0 &&
           value.digit[highest] == 0)
    {
        --highest;
    }

    appendUnsigned(
        output,
        value.digit[highest]
    );

    for (int i = highest - 1; i >= 0; --i)
    {
        appendPaddedNine(
            output,
            value.digit[i]
        );
    }
}

void main()
{
    FastScanner scanner;

    int n = scanner.nextInt();
    int m = scanner.nextInt();

    RawEdge[] rawEdges = new RawEdge[m];
    int[] degree = new int[n];

    // maximumExponent[p]は、いずれかのb_iに現れる
    // 素数pの指数の最大値。
    int[] maximumExponent =
        new int[MAX_AB + 1];

    foreach (i; 0 .. m)
    {
        int u = scanner.nextInt() - 1;
        int v = scanner.nextInt() - 1;
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        rawEdges[i] = RawEdge(u, v, a, b);

        ++degree[u];
        ++degree[v];

        int value = b;

        for (int prime = 2;
             prime * prime <= value;
             ++prime)
        {
            if (value % prime != 0)
            {
                continue;
            }

            int exponent = 0;

            while (value % prime == 0)
            {
                value /= prime;
                ++exponent;
            }

            if (exponent >
                maximumExponent[prime])
            {
                maximumExponent[prime] =
                    exponent;
            }
        }

        if (value > 1 &&
            maximumExponent[value] == 0)
        {
            maximumExponent[value] = 1;
        }
    }

    FixedInt commonDenominator =
        FixedInt.one();

    PrimePower[] primePowers;

    foreach (prime; 2 .. MAX_AB + 1)
    {
        int exponent =
            maximumExponent[prime];

        if (exponent == 0)
        {
            continue;
        }

        primePowers ~=
            PrimePower(prime, exponent);

        foreach (_; 0 .. exponent)
        {
            commonDenominator.multiplySmall(
                cast(uint)prime
            );
        }
    }

    // CSR形式でグラフを構築する。
    size_t[] offset = new size_t[n + 1];

    foreach (vertex; 0 .. n)
    {
        offset[vertex + 1] =
            offset[vertex] +
            cast(size_t)degree[vertex];
    }

    size_t[] cursor = offset.dup;
    Edge[] edges = new Edge[2 * m];

    foreach (ref raw; rawEdges)
    {
        FixedInt scaledWeight =
            commonDenominator;

        scaledWeight.divideSmall(
            cast(uint)raw.denominator
        );

        scaledWeight.multiplySmall(
            cast(uint)raw.numerator
        );

        size_t first = cursor[raw.u]++;
        size_t second = cursor[raw.v]++;

        edges[first] =
            Edge(raw.v, scaledWeight);

        edges[second] =
            Edge(raw.u, scaledWeight);
    }

    FixedInt[] distance =
        new FixedInt[n];

    bool[] reached =
        new bool[n];

    MinHeap queue =
        MinHeap(cast(size_t)n, distance);

    reached[0] = true;
    queue.pushOrDecrease(0);

    while (!queue.empty)
    {
        int current = queue.pop();

        foreach (
            edgeIndex;
            offset[current] ..
            offset[current + 1]
        )
        {
            ref Edge edge =
                edges[edgeIndex];

            FixedInt nextDistance =
                distance[current];

            nextDistance.addAssign(
                edge.weight
            );

            if (!reached[edge.to] ||
                nextDistance.compare(
                    distance[edge.to]
                ) < 0)
            {
                reached[edge.to] = true;
                distance[edge.to] =
                    nextDistance;

                queue.pushOrDecrease(
                    edge.to
                );
            }
        }
    }

    auto output = appender!string();
    output.reserve(
        8U * 1024U * 1024U
    );

    foreach (vertex; 1 .. n)
    {
        FixedInt numerator =
            distance[vertex];

        FixedInt denominator =
            commonDenominator;

        // 分母の素因数分解は既知なので、
        // 小さい素数だけで約分する。
        foreach (
            ref primePower;
            primePowers
        )
        {
            foreach (
                _;
                0 .. primePower.exponent
            )
            {
                uint prime =
                    cast(uint)primePower.prime;

                if (numerator.modulusSmall(
                        prime
                    ) != 0)
                {
                    break;
                }

                numerator.divideSmall(prime);
                denominator.divideSmall(prime);
            }
        }

        appendFixedInt(
            output,
            numerator
        );

        output.put(' ');

        appendFixedInt(
            output,
            denominator
        );

        output.put('\n');
    }

    auto data = output.data;

    fwrite(
        data.ptr,
        1,
        data.length,
        stdout
    );
}