#655876 (C++14) No.1502 Many Simple Additions

提出ソース

結果

問題	No.1502 Many Simple Additions
ユーザー	Iván Soto
提出日時	2021-05-09 21:00:39
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,692 bytes
コンパイル時間	2,359 ms
コンパイル使用メモリ	188,612 KB
実行使用メモリ	20,524 KB
最終ジャッジ日時	2023-10-19 05:31:30
合計ジャッジ時間	8,680 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	WA	-
testcase_06	AC	2 ms 4,348 KB
testcase_07	WA	-
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	WA	-
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 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	AC	2 ms 4,348 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	55 ms 17,884 KB
testcase_28	AC	54 ms 18,148 KB
testcase_29	AC	1,340 ms 14,188 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	33 ms 5,028 KB
testcase_37	AC	32 ms 5,028 KB
testcase_38	AC	50 ms 8,252 KB
testcase_39	AC	29 ms 5,684 KB
testcase_40	AC	128 ms 9,308 KB
testcase_41	AC	88 ms 6,404 KB
testcase_42	AC	283 ms 18,216 KB
testcase_43	AC	2 ms 4,348 KB

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

ソースコード

raw source code

/**
 *  author: ivanzuki   
 *  created: Sat May 08 2021
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
template<typename T> void dout(string name, int idx, T arg) {
  cerr << name << " = " << to_string(arg);
}

template<typename T1, typename... T2> void dout(string names, int idx, T1 arg, T2... args) {
  cerr << names.substr(0, names.find(',')) << " = " << to_string(arg) << ", ";
  dout(names.substr(names.find(',') + 2), idx + 1, args...);
}

#ifdef LOCAL
#define debug(...) cerr << "[", dout(#__VA_ARGS__, 0, __VA_ARGS__), cerr << "]" << endl;
#else
#define debug(...) 42
#endif

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}
 
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
 
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
 
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
 
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }
 
  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }
 
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
 
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
 
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) { return v; }
 
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
 
 private:
  Type value;
};
 
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
 
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
 
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
 
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
 
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
 
/*
using ModType = int;
 
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/
 
constexpr int md = (int) 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
const int inf = (int) 1e9;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  vector<int> was(n);
  vector<int> value(n, -1);
  vector<int> depth(n);
  int cc = 0;
  vector<int> can(n, 1);
  vector<int> l(n, -inf), r(n, inf);
  vector<Mint> all_ways(n), inner_ways(n);
  vector<set<int>> needs(n);
  function<void(int)> DFS = [&](int v) {
    was[v] = 1;
    if (depth[v] % 2 == 0) {
      if (value[v] > k) {
        can[cc] = 0;
      } else {
        l[cc] = max(l[cc], -value[v] + 1);
        r[cc] = min(r[cc], k - value[v]);
      }
    } else {
      if (value[v] >= k) {
        l[cc] = max(l[cc], value[v] - k);
      }
      r[cc] = min(r[cc], value[v] - 1);
    }
    for (const auto& e : g[v]) {
      int u = e.first, w = e.second;
      if (was[u] == 0) {
        value[u] = w - value[v];
        depth[u] = depth[v] + 1;
        DFS(u);
      } else {
        if (depth[v] % 2 == depth[u] % 2) {
          if (abs(w - (value[v] + value[u])) % 2 == 0) {
            if (depth[v] % 2 == 0) {
              int need = (w - (value[v] + value[u])) / 2;
              if (need < 0) {
                can[cc] = 0;
              } else {
                needs[cc].insert(need);
              }
            } else {
              int need = ((value[v] + value[u]) - w) / 2;
              if (need < 0) {
                can[cc] = 0;
              } else {
                needs[cc].insert(need);
              }
            }
          } else {
            can[cc] = 0;
          }
        } else {
          if (value[v] + value[u] != w) {
            can[cc] = 0;
          }
        }
      }
    }
  };
  Mint ans = 1;
  vector<int> value_k(n);
  vector<int> was_k(n);
  function<int(int)> TheMax = [&](int v) {
    was_k[v] = 1;
    int ret = value_k[v];
    for (const auto& e : g[v]) {
      int u = e.first, w = e.second;
      value_k[u] = w - value_k[v];
      if (!was_k[u]) {
        ret = max(ret, TheMax(u));
      }
    }
    return ret;
  };
  for (int i = 0; i < n; i++) {
    if (was[i] == 0) {
      value[i] = 1;
      DFS(i);
      if (!can[cc]) {
        ans = 0;
      } else {
        auto Doable = [&](const set<int>& needs) {
          int last = -1;
          for (const auto& t : needs) {
            if (t != l[cc] && t != r[cc]) {
              return false;
            }
            if (last != -1) {
              if (t != last) {
                return false;
              }
            }
            last = t;
          }
          return true;
        };
        if (l[cc] > r[cc] || l[cc] < 0 || !Doable(needs[cc])) {
          can[cc] = 0;
        } else {
          value_k[i] = l[cc] + 1;
          // all_ways[cc] = 1 + (l[cc] < r[cc]);
          // debug(TheMax(i));
          bool left = (TheMax(i) == k && (needs[cc].empty() || *needs[cc].begin() == l[cc]));
          debug(all_ways[cc]);
          value_k[i] = r[cc] + 1;
          fill(was_k.begin(), was_k.end(), 0);
          // debug(TheMax(i));
          bool right = (l[cc] < r[cc] && TheMax(i) == k && (needs[cc].empty() || *needs[cc].begin() == r[cc]));
          debug(all_ways[cc]);
          all_ways[cc] = left + right;
          inner_ways[cc] = max(0, r[cc] - l[cc] - 1 + !left + !right);
        }
        ans *= (all_ways[cc] + inner_ways[cc]);
      }
      ++cc;
    }
  }
  if (ans == 0) {
    debug(ans, l, r, cc, all_ways, inner_ways, can, needs);
    cout << ans << '\n';
  } else {
    Mint remove = 1;
    for (int i = 0; i < cc; i++) {
      remove *= inner_ways[i];
    }
    debug(ans, remove, l, r, cc, all_ways, inner_ways, needs);
    ans -= remove;
    cout << ans << '\n';
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード