結果

問題 No.1502 Many Simple Additions
コンテスト
ユーザー firiexp
提出日時 2021-05-07 22:43:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
(最新)
CE  
(最初)
実行時間 -
コード長 6,478 bytes
コンパイル時間 4,609 ms
コンパイル使用メモリ 152,268 KB
最終ジャッジ日時 2025-01-21 08:31:38
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21 WA * 7 TLE * 10 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

struct QuickFind {
    int n;
    vector<int> roots;
    vector<vector<int>> v;
    explicit QuickFind(int n) : n(n) {
        v.resize(n);
        for (int i = 0; i < n; ++i) v[i].emplace_back(i);
        roots.resize(n);
        iota(roots.begin(),roots.end(), 0);
    }

    int root(int a){ return roots[a]; }
    size_t size(int a){ return v[a].size(); }
    bool unite(int a, int b){
        if(same(a, b)) return false;
        a = roots[a], b = roots[b];
        if(size(a) < size(b)) swap(a, b);
        for (auto &&i : v[b]) {
            v[a].emplace_back(i);
            roots[i] = a;
        }
        v[b].clear();
        v[b].shrink_to_fit();
        return true;
    }
    bool same(int a, int b){ return roots[a] == roots[b]; }
    const vector<int>& components(int x){ return v[roots[x]];}
};
template <u32 M>
struct modint {
    u32 val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = u32(x); }
    modint(bool v) { val = ((unsigned int)(v) % M); }
    modint& operator++() { val++; if (val == M) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = M; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }
    modint& operator*=(const modint& b) { u64 z = val; z *= b.val; val = (u32)(z % M); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(M-2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<ll, ll>>> G(n);
    QuickFind uf(n);
    for (int i = 0; i < m; ++i) {
        ll u, v; ll s;
        cin >> u >> v >> s;
        G[u-1].emplace_back(v-1, s);
        G[v-1].emplace_back(u-1, s);
        uf.unite(u-1, v-1);
    }
    mint ans = 1, ans2 = 0;
    vector<pair<ll, ll>> v(n, make_pair(0, 0));
    auto solve = [&](int root) -> void {
        for (auto &&i : uf.components(root)) {
            v[i] = {0, 0};
        }
        v[root] = make_pair(1, 0);
        pair<ll, ll> s{0, 0};
        queue<ll> q;
        q.emplace(0);
        while(!q.empty()){
            ll f = q.front(); q.pop();
            for (auto &&i : G[f]) {
                ll to, cost; tie(to, cost) = i;
                if(v[to].first == 0) {
                    q.emplace(to);
                    v[to] = make_pair(-v[f].first, cost-v[f].second);
                }else if(v[to].first != v[f].first){
                    if(v[to].second != cost-v[f].second){
                        ans = ans2 = 0;
                        return;
                    }
                }else {
                    ll x = (cost-v[to].second-v[f].second);
                    if((x+INF<ll>+1)%2 || x/(2*v[f].first) <= 0){
                        ans = ans2 = 0;
                        return;
                    }else {
                        s = make_pair(2, x/(2*v[f].first));
                        while(!q.empty()) q.pop();
                        break;
                    }
                }
            }
        }
        if(s == make_pair(0LL, 0LL)){
            ll a = 1, b = k;
            ll a2 = 1, b2 = k-1;
            for (auto &&i : uf.components(root)) {
                if(v[i].first > 0) {
                    a = max(a, 1-v[i].second);
                    b = min(b, k-v[i].second);
                    a2 = max(a2, 1-v[i].second);
                    b2 = min(b2, k-1-v[i].second);
                } else {
                    a = max(a, v[i].second-k);
                    b = min(b, v[i].second-1);
                    a2 = max(a2, v[i].second-(k-1));
                    b2 = min(b2, v[i].second-1);
                }
            }
            mint ans3 = max(b2-a2+1, 0LL)*ans, ans4 = (max(b-a+1, 0LL)-max(b2-a2+1, 0LL))*ans+ans2*max(b-a+1, 0LL);
            ans = ans3; ans2 = ans4;
            return ;
        }else {
            vector<ll> va(n, 0);
            va[0] = s.second;
            q.emplace(0);
            bool valid = true, pi = s.second == k;
            while(!q.empty()){
                ll f = q.front(); q.pop();
                for (auto &&i : G[f]) {
                    ll to, cost; tie(to, cost) = i;
                    if(va[to]){
                        if(va[to]+va[f] != cost) valid = false;
                    }else {
                        if(cost-va[f] <= 0 || cost-va[f] > k) {
                            valid = false;
                        }else {
                            pi |= cost-va[f] == k;
                            va[to] = cost - va[f];
                            q.emplace(to);
                        }
                    }
                }
            }
            if(!valid) {
                ans = ans2 = 0;
                return;
            }
            if(pi) ans2 += ans, ans = 0;
            return;
        }
    };
    for (int i = 0; i < n; ++i) {
        if(uf.root(i) == i) solve(i);
    }
    cout << ans2.val << "\n";
    return 0;
}
0