結果
| 問題 | No.1502 Many Simple Additions |
| ユーザー |
 firiexp
|
| 提出日時 | 2021-05-07 22:49:06 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,395 bytes |
| コンパイル時間 | 766 ms |
| コンパイル使用メモリ | 100,656 KB |
| 最終ジャッジ日時 | 2023-10-13 22:34:55 |
| 合計ジャッジ時間 | 1,481 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:18:21: エラー: ‘::numeric_limits’ has not been declared
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ^~~~~~~~~~~~~~
main.cpp:18:37: エラー: expected primary-expression before ‘>’ token
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ^
main.cpp:18:43: エラー: ‘max()’ の呼び出しに適合する関数がありません
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ~~~~~^~
次のファイルから読み込み: /usr/local/gcc7/include/c++/12.2.0/string:50,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/locale_classes.h:40,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/ios_base.h:41,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ios:42,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ostream:38,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/iostream:39,
次から読み込み: main.cpp:1:
/usr/local/gcc7/include/c++/12.2.0/bits/stl_algobase.h:254:5: 備考: 候補: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/local/gcc7/include/c++/12.2.0/bits/stl_algobase.h:254:5: 備考: template argument deduction/substitution failed:
main.cpp:18:43: 備考: 候補では 2 個の引数が予期されますが、0 個の引数が与えられています
18 | constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
| ~~~~~^~
/usr/local/gcc7/include/c++/12.2.0/bits/stl_algobase.h:300:5: 備考: 候補: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr
ソースコード
#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;
}