#940899 (C++23) No.1502 Many Simple Additions

提出ソース

結果

問題	No.1502 Many Simple Additions
ユーザー	👑 rin204
提出日時	2023-12-29 00:09:45
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	62 ms / 2,000 ms
コード長	12,547 bytes
コンパイル時間	3,495 ms
コンパイル使用メモリ	264,224 KB
実行使用メモリ	16,196 KB
最終ジャッジ日時	2024-09-27 15:56:11
合計ジャッジ時間	6,836 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	53 ms 16,148 KB
testcase_28	AC	53 ms 16,128 KB
testcase_29	AC	21 ms 16,196 KB
testcase_30	AC	62 ms 16,128 KB
testcase_31	AC	62 ms 16,000 KB
testcase_32	AC	61 ms 16,128 KB
testcase_33	AC	41 ms 6,940 KB
testcase_34	AC	43 ms 6,944 KB
testcase_35	AC	42 ms 6,944 KB
testcase_36	AC	31 ms 6,944 KB
testcase_37	AC	31 ms 6,940 KB
testcase_38	AC	4 ms 6,944 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	5 ms 6,940 KB
testcase_41	AC	9 ms 6,944 KB
testcase_42	AC	21 ms 6,944 KB
testcase_43	AC	2 ms 6,940 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#include <bits/stdc++.h>

template <typename T = long long>
struct UnionFindSumConstraints {
    int n;
    std::vector<int> par;
    int group;
    // 根を x としたとき、A[i] = (pm[i] ? 1 : -1) x + B[i]
    std::vector<bool> pm;
    std::vector<T> B;
    // unique: 一意に定まるか
    // X2: 一意に定まる場合、根の値の 2 倍を記録
    std::vector<bool> unique;
    std::vector<T> X2;

    UnionFindSumConstraints(int n) : n(n), group(n) {
        par.assign(n, -1);
        pm.assign(n, true);
        B.assign(n, T(0));
        unique.assign(n, false);
        X2.assign(n, T(0));
    }

    int find(int x) {
        if (par[x] < 0) return x;
        int p = par[x];
        if (par[p] < 0) return p;
        find(par[x]);
        if (pm[x]) {
            pm[x] = pm[p];
            B[x] += B[p];
        } else {
            pm[x] = !pm[p];
            B[x] -= B[p];
        }
        par[x] = par[p];
        return par[x];
    }

    bool can_unite(int x, int y, T z) {
        // A[x] + A[y] == z
        int xp = find(x);
        int yp = find(y);
        if (xp == yp) {
            int p = xp;
            if (pm[x] != pm[y]) {
                return B[x] + B[y] == z;
            } else {
                if (unique[p]) {
                    if (pm[x]) {
                        return B[x] + B[y] + X2[p] == z;
                    } else {
                        return B[x] + B[y] - X2[p] == z;
                    }
                } else {
                    unique[p] = true;
                    if (pm[x]) {
                        X2[p] = z - B[x] - B[y];
                    } else {
                        X2[p] = B[x] + B[y] - z;
                    }
                    return true;
                }
            }
        } else {
            if (!unique[xp] or !unique[yp]) {
                return true;
            }
            T x2 = (pm[x] ? X2[xp] : -X2[xp]) + B[x] * 2;
            T y2 = (pm[y] ? X2[yp] : -X2[yp]) + B[y] * 2;
            return x2 + y2 == 2 * z;
        }
    }

    bool unite(int x, int y, T z) {
        // A[x] + A[y] == z
        assert(can_unite(x, y, z));

        int xp = find(x);
        int yp = find(y);
        if (xp == yp) {
            int p = xp;
            if (pm[x] != pm[y]) {
                assert(B[x] + B[y] == z);
            } else {
                if (!unique[p]) {
                    unique[p] = true;
                    if (pm[x]) {
                        X2[p] = z - B[x] - B[y];
                    } else {
                        X2[p] = B[x] + B[y] - z;
                    }
                }
            }
            return false;
        }
        if (par[xp] > par[yp]) {
            std::swap(x, y);
            std::swap(xp, yp);
        }

        group--;
        par[xp] += par[yp];
        par[yp] = xp;
        T tmp   = z - B[x] - B[y];
        B[yp]   = pm[y] ? tmp : -tmp;
        pm[yp]  = pm[x] ^ pm[y];

        if (!unique[xp] and unique[yp]) {
            T tmp      = X2[yp] - 2 * B[yp];
            X2[xp]     = (pm[yp] ? tmp : -tmp);
            unique[xp] = true;
        }

        return true;
    }

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

    int size(int x) {
        return -par[find(x)];
    }

    std::vector<int> roots() {
        std::vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (i == find(i)) ret.push_back(i);
        }
        return ret;
    }

    bool isroot(int x) {
        return x == find(x);
    }
};

template <int MOD>
struct Modint {
    int x;
    Modint() : x(0) {}
    Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }

    Modint &operator+=(const Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Modint &operator-=(const Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }

    Modint &operator*=(const Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Modint &operator/=(const Modint &p) {
        *this *= p.inverse();
        return *this;
    }

    Modint &operator%=(const Modint &p) {
        assert(p.x == 0);
        return *this;
    }

    Modint operator-() const {
        return Modint(-x);
    }

    Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }

    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }

    friend Modint operator+(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) += rhs;
    }

    friend Modint operator-(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) -= rhs;
    }

    friend Modint operator*(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) *= rhs;
    }

    friend Modint operator/(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) /= rhs;
    }

    friend Modint operator%(const Modint &lhs, const Modint &rhs) {
        assert(rhs.x == 0);
        return Modint(lhs);
    }

    bool operator==(const Modint &p) const {
        return x == p.x;
    }

    bool operator!=(const Modint &p) const {
        return x != p.x;
    }

    bool operator<(const Modint &rhs) const {
        return x < rhs.x;
    }

    bool operator<=(const Modint &rhs) const {
        return x <= rhs.x;
    }

    bool operator>(const Modint &rhs) const {
        return x > rhs.x;
    }

    bool operator>=(const Modint &rhs) const {
        return x >= rhs.x;
    }

    Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Modint(u);
    }

    Modint pow(int64_t k) const {
        Modint ret(1);
        Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend std::ostream &operator<<(std::ostream &os, const Modint &p) {
        return os << p.x;
    }

    friend std::istream &operator>>(std::istream &is, Modint &p) {
        int64_t y;
        is >> y;
        p = Modint<MOD>(y);
        return (is);
    }

    static int get_mod() {
        return MOD;
    }
};

struct Arbitrary_Modint {
    int x;
    static int MOD;

    static void set_mod(int mod) {
        MOD = mod;
    }

    Arbitrary_Modint() : x(0) {}
    Arbitrary_Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }

    Arbitrary_Modint &operator+=(const Arbitrary_Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Arbitrary_Modint &operator-=(const Arbitrary_Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }

    Arbitrary_Modint &operator*=(const Arbitrary_Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Arbitrary_Modint &operator/=(const Arbitrary_Modint &p) {
        *this *= p.inverse();
        return *this;
    }

    Arbitrary_Modint &operator%=(const Arbitrary_Modint &p) {
        assert(p.x == 0);
        return *this;
    }

    Arbitrary_Modint operator-() const {
        return Arbitrary_Modint(-x);
    }

    Arbitrary_Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Arbitrary_Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Arbitrary_Modint operator++(int) {
        Arbitrary_Modint result = *this;
        ++*this;
        return result;
    }

    Arbitrary_Modint operator--(int) {
        Arbitrary_Modint result = *this;
        --*this;
        return result;
    }

    friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) += rhs;
    }

    friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) -= rhs;
    }

    friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) *= rhs;
    }

    friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) /= rhs;
    }

    friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        assert(rhs.x == 0);
        return Arbitrary_Modint(lhs);
    }

    bool operator==(const Arbitrary_Modint &p) const {
        return x == p.x;
    }

    bool operator!=(const Arbitrary_Modint &p) const {
        return x != p.x;
    }

    bool operator<(const Arbitrary_Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Arbitrary_Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Arbitrary_Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Arbitrary_Modint &rhs) {
        return x >= rhs.x;
    }

    Arbitrary_Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Arbitrary_Modint(u);
    }

    Arbitrary_Modint pow(int64_t k) const {
        Arbitrary_Modint ret(1);
        Arbitrary_Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend std::ostream &operator<<(std::ostream &os, const Arbitrary_Modint &p) {
        return os << p.x;
    }

    friend std::istream &operator>>(std::istream &is, Arbitrary_Modint &p) {
        int64_t y;
        is >> y;
        p = Arbitrary_Modint(y);
        return (is);
    }

    static int get_mod() {
        return MOD;
    }
};
int Arbitrary_Modint::MOD = 998244353;

using modint9 = Modint<998244353>;
using modint1 = Modint<1000000007>;
using modint  = Arbitrary_Modint;
using mint    = modint1;

void solve() {
    int n, m;
    long long k;
    cin >> n >> m >> k;
    UnionFindSumConstraints UF(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        long long z;
        cin >> x >> y >> z;
        x--;
        y--;
        if (!UF.can_unite(x, y, z)) {
            cout << 0 << endl;
            return;
        }
        UF.unite(x, y, z);
    }

    const long long inf = 1LL << 60;
    vector<vector<long long>> plus(n, {inf, -inf}), minus(n, {inf, -inf});
    for (int i = 0; i < n; i++) {
        int p = UF.find(i);
        if (UF.unique[p] and UF.X2[p] % 2 == 1) {
            cout << 0 << endl;
            return;
        }
        if (UF.pm[i]) {
            plus[p][0] = min(plus[p][0], UF.B[i]);
            plus[p][1] = max(plus[p][1], UF.B[i]);
        } else {
            minus[p][0] = min(minus[p][0], UF.B[i]);
            minus[p][1] = max(minus[p][1], UF.B[i]);
        }
    }

    auto f = [&](long long k) -> mint {
        mint ret = 1;
        for (int i = 0; i < n; i++) {
            if (!UF.isroot(i)) {
                continue;
            }
            if (UF.size(i) == 1) {
                ret *= k;
                continue;
            }

            long long lp = 1 - plus[i][0];
            long long rp = k - plus[i][1];

            long long lm = minus[i][1] - k;
            long long rm = minus[i][0] - 1;
            if (rp < lp or rm < lm) {
                return 0;
            }
            if (rp < lm or rm < lp) {
                return 0;
            }
            long long l = max(lp, lm);
            long long r = min(rp, rm);

            if (UF.unique[i]) {
                if (UF.X2[i] < 2 * l or 2 * r < UF.X2[i]) {
                    return 0;
                }
            } else {
                ret *= r - l + 1;
            }
        }

        return ret;
    };

    mint ans = f(k) - f(k - 1);
    cout << ans << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード