結果
| 問題 | No.1502 Many Simple Additions |
| ユーザー |
 firiexp
|
| 提出日時 | 2021-05-07 22:49:06 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,395 bytes |
| コンパイル時間 | 1,984 ms |
| コンパイル使用メモリ | 106,648 KB |
| 最終ジャッジ日時 | 2025-03-30 15:37:02 |
| 合計ジャッジ時間 | 3,503 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:18:21: error: '::numeric_limits' has not been declared
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ^~~~~~~~~~~~~~
main.cpp:18:37: error: expected primary-expression before '>' token
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ^
main.cpp:18:43: error: no matching function for call to 'max()'
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/iostream:39,
from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
main.cpp:18:43: note: candidate expects 2 arguments, 0 provided
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp&
ソースコード
#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));vector<ll> va(n, 0);auto solve = [&](int root) -> void {v[root] = make_pair(1, 0);pair<ll, ll> s{0, 0};queue<ll> q;q.emplace(root);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 {va[root] = s.second;q.emplace(root);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;}