結果

問題 No.1502 Many Simple Additions
ユーザー suisensuisen
提出日時 2021-05-08 02:17:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,696 bytes
コンパイル時間 2,186 ms
コンパイル使用メモリ 210,032 KB
実行使用メモリ 13,312 KB
最終ジャッジ日時 2024-09-15 16:33:50
合計ジャッジ時間 5,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 WA -
testcase_07 AC 2 ms
6,944 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 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,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 47 ms
10,112 KB
testcase_28 AC 47 ms
10,368 KB
testcase_29 AC 6 ms
6,940 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 31 ms
6,944 KB
testcase_37 WA -
testcase_38 AC 43 ms
7,504 KB
testcase_39 AC 25 ms
6,940 KB
testcase_40 AC 18 ms
6,944 KB
testcase_41 AC 4 ms
6,940 KB
testcase_42 AC 63 ms
11,264 KB
testcase_43 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#pragma region

using namespace std;

// ! type aliases
using int128 = __int128_t;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;

template <typename T>
using vec = std::vector<T>;
template <typename T>
using vec2 = vec<vec<T>>;
template <typename T>
using vec3 = vec<vec2<T>>;

template <typename T>
using pq_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <typename T, typename U>
using umap = unordered_map<T, U>;

// ! macros
#define rep(i, n)           for (int i = 0; i < n; ++i)
#define reps(i, n, s)       for (int i = 0; i < n; i += s)
#define replr(i, l, r)      for (int i = l; i < r; ++i)
#define replrs(i, l, r, s)  for (int i = l; i < r; i += s)
#define rrep(i, n)          for (int i = (n) - 1; i >= 0; --i)
#define rreps(i, n, s)      for (int i = (n) - 1; i >= 0; i -= s)
#define rreplr(i, l, r)     for (int i = (r) - 1; i >= l; --i)
#define rreplrs(i, l, r, s) for (int i = (r) - 1; i >= l; i -= s)

#define all(iterable) (iterable).begin(), (iterable).end()

// ! constants
constexpr int dx4[4] = {1, 0, -1, 0};
constexpr int dy4[4] = {0, 1, 0, -1};

constexpr int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

constexpr int IINF = (1 << 30) - 1;
constexpr ll LINF = (1LL << 62) - 1; 

// ! I/O utilities
inline void print() { cout << '\n'; }
template <typename Head, typename... Tail>
inline void print(const Head& head, const Tail&... tails) {
    cout << head;
    if (sizeof...(tails)) cout << ' ';
    print(tails...);
}
template <typename T>
void print(const vec<T>& v, const string sep = " ", const string end = "\n") {
    int n = v.size();
    rep(i, n) cout << v[i] << (i < n - 1 ? sep : end);
}
template <typename T>
void print(const vec<T>& v, const size_t begin_index, const size_t length, const string sep = " ", const string end = "\n") {
    int n = begin_index + length;
    replr(i, begin_index, n) cout << v[i] << (i < n - 1 ? sep : end);
}
constexpr void read() {}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail& ...tails) {
    cin >> head;
    read(tails...);
}
template <typename T>
void read(vec<T>& a, size_t begin_index, size_t length) {
    a.resize(begin_index + length);
    while (length --> 0) cin >> a[begin_index++];
}
template <typename T>
void read(vec<T>& a) {
    read(a, 0, a.size());
}

// ! utility functions
template <typename T>
bool chmin(T &x, T &y) {
    if (y < x) {
        x = y;
        return true;
    } else return false;
}
template <typename T>
bool chmin(T &x, T &&y) {
    if (y < x) {
        x = y;
        return true;
    } else return false;
}
template <typename T>
bool chmax(T &x, T &y) {
    if (x < y) {
        x = y;
        return true;
    } else return false;
}
template <typename T>
bool chmax(T &x, T &&y) {
    if (x < y) {
        x = y;
        return true;
    } else return false;
}

#pragma endregion

// ! code from here

constexpr ll mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    read(n, m, k);
    vec<vec<pair<int, int>>> g(n);
    rep(i, m) {
        int u, v, w;
        read(u, v, w);
        --u, --v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vec<pair<int, int>> range(n, {IINF, IINF});
    vec<char> vis(n, false);
    auto dfs = [&](auto self, int u, int p, int l, int r, int max_val) -> void {
        vis[u] = true;
        for (auto [v, w] : g[u]) {
            if (v == p) continue;
            if (not vis[v]) {
                int nl = max(w - r, 1);
                int nr = min(w - l, max_val);
                self(self, v, u, nl, nr, max_val);
            }
        }
        for (auto [v, w] : g[u]) {
            if (v == p or range[v].first == IINF) continue;
            auto [vl, vr] = range[v];
            int nl = max(w - vr, 1);
            int nr = min(w - vl, max_val);
            chmax(l, nl);
            chmin(r, nr);
        }
        if (l <= r) range[u] = {l, r};
        else range[u] = {0, -1};
    };
    ll ans1 = 1;
    rep(i, n) {
        if (not vis[i]) {
            dfs(dfs, i, -1, 1, k, k);
            auto [l, r] = range[i];
            (ans1 *= max(r - l + 1, 0)) %= mod;
        }
    }
    // print(ans1);
    vis.assign(n, false);
    range.assign(n, {IINF, IINF});
    ll ans2 = 1;
    rep(i, n) {
        if (not vis[i]) {
            dfs(dfs, i, -1, 1, k - 1, k - 1);
            auto [l, r] = range[i];
            (ans2 *= max(r - l + 1, 0)) %= mod;
        }
    }
    // print(ans2);
    ll ans = (ans1 - ans2) % mod;
    if (ans < 0) ans += mod;
    print(ans);
    return 0;
}
0