結果

問題 No.1502 Many Simple Additions
ユーザー suisen
提出日時 2021-05-08 02:17:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,696 bytes
コンパイル時間 2,208 ms
コンパイル使用メモリ 204,892 KB
最終ジャッジ日時 2025-01-21 09:06:41
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20 WA * 19
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0