結果

問題 No.1502 Many Simple Additions
ユーザー kwm_tkwm_t
提出日時 2021-05-13 09:49:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 3,272 bytes
コンパイル時間 3,702 ms
コンパイル使用メモリ 232,472 KB
実行使用メモリ 17,732 KB
最終ジャッジ日時 2024-09-24 23:19:45
合計ジャッジ時間 5,885 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,384 KB
testcase_01 AC 4 ms
8,260 KB
testcase_02 AC 4 ms
8,516 KB
testcase_03 AC 4 ms
8,900 KB
testcase_04 AC 5 ms
9,540 KB
testcase_05 AC 4 ms
9,792 KB
testcase_06 AC 4 ms
9,668 KB
testcase_07 AC 3 ms
8,256 KB
testcase_08 AC 4 ms
8,644 KB
testcase_09 AC 3 ms
8,512 KB
testcase_10 AC 4 ms
9,032 KB
testcase_11 AC 4 ms
9,544 KB
testcase_12 AC 4 ms
9,412 KB
testcase_13 AC 4 ms
8,648 KB
testcase_14 AC 4 ms
8,904 KB
testcase_15 AC 4 ms
9,412 KB
testcase_16 AC 4 ms
9,672 KB
testcase_17 AC 3 ms
8,520 KB
testcase_18 AC 4 ms
8,520 KB
testcase_19 AC 4 ms
8,264 KB
testcase_20 AC 4 ms
9,668 KB
testcase_21 AC 3 ms
8,392 KB
testcase_22 AC 4 ms
8,640 KB
testcase_23 AC 4 ms
8,904 KB
testcase_24 AC 4 ms
9,288 KB
testcase_25 AC 4 ms
9,416 KB
testcase_26 AC 4 ms
9,156 KB
testcase_27 AC 47 ms
14,916 KB
testcase_28 AC 47 ms
15,044 KB
testcase_29 AC 9 ms
10,948 KB
testcase_30 AC 69 ms
17,732 KB
testcase_31 AC 69 ms
17,472 KB
testcase_32 AC 67 ms
17,604 KB
testcase_33 AC 54 ms
14,660 KB
testcase_34 AC 57 ms
15,428 KB
testcase_35 AC 54 ms
15,812 KB
testcase_36 AC 36 ms
11,968 KB
testcase_37 AC 34 ms
11,588 KB
testcase_38 AC 40 ms
12,996 KB
testcase_39 AC 25 ms
10,304 KB
testcase_40 AC 15 ms
10,308 KB
testcase_41 AC 6 ms
10,436 KB
testcase_42 AC 50 ms
16,072 KB
testcase_43 AC 4 ms
9,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
using namespace atcoder;
using mint = modint1000000007;
const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
//const bool debug = false;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }

struct Edge {
	int to, cost;
	Edge(int _to, int _cost) :to(_to), cost(_cost) {}
};
vector<Edge>g[200005];
long long a[200005];
long long b[200005];
vector<int>w;
bool ng;
long long val;
void dfs(int v, int p = -1) {
	w.push_back(v);
	for (Edge e : g[v]) {
		//if (p == e.to) continue;
		if (0 == a[e.to]) {
			a[e.to] = -a[v];
			b[e.to] = e.cost - b[v];
			dfs(e.to, v);
		}
		else if (a[v] != a[e.to]) {
			if (e.cost != b[v] + b[e.to]) {
				ng = true;
				break;
			}
		}
		else {
			if (-1 == val) {
				if (0 != (e.cost - b[v] - b[e.to]) % 2) {
					ng = true;
					break;
				}
				int nval = ((e.cost - b[v] - b[e.to]) / 2) *a[v];
				if (nval <= 0) {
					ng = true;
					break;
				}
				val = nval;
			}
			else {
				int s = a[v] * val + b[v];
				int t = a[e.to] * val + b[e.to];
				if (e.cost != s + t) {
					ng = true;
					break;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, k;
	cin >> n >> m >> k;
	vector<int>x(m), y(m), z(m);
	dsu uf(n);
	rep(i, m) {
		int x, y, z;
		cin >> x >> y >> z;
		x--; y--;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
	}
	mint c1 = 1, c2 = 1;
	rep(i, n) {
		if (0 != a[i]) continue;
		a[i] = 1; b[i] = 0;
		w.clear();
		val = -1;
		dfs(i);
		if (ng) {
			cout << 0 << endl;
			return 0;
		}
		if (-1 == val) {
			{
				long long l = 1;
				long long r = k;
				rep(j, w.size()) {
					if (1 == a[w[j]]) {
						//0 < x + b[] <= k
						// -b[] < x <= k-x
						chmax(l, 1 - b[w[j]]);
						chmin(r, k - b[w[j]]);
					}
					else {
						//0 < -x+b[] <= k
						// b[]-k <= x < b[]
						chmax(l, b[w[j]] - k);
						chmin(r, b[w[j]] - 1);
					}
				}
				c1 *= max(0LL, r - l + 1);
			}
			{
				long long l = 1;
				long long r = k - 1;
				rep(j, w.size()) {
					if (1 == a[w[j]]) {
						//0 < x + b[] <= k - 1
						// -b[] < x <= k - 1 -x
						chmax(l, 1 - b[w[j]]);
						chmin(r, (k - 1) - b[w[j]]);
					}
					else {
						//0 < -x+b[] <= k - 1
						// b[]-(k - 1) <= x < b[]
						chmax(l, b[w[j]] - (k - 1));
						chmin(r, b[w[j]] - 1);
					}
				}
				c2 *= max(0LL, r - l + 1);
			}
		}
		else {
			rep(j, w.size()) {
				long long x = a[w[j]] * val + b[w[j]];
				if (x <= 0) {
					cout << 0 << endl;
					return 0;
				}
				else if (x == k) {
					c2 = 0;
				}
				else if (x > k) {
					cout << 0 << endl;
					return 0;
				}
			}
		}
	}
	cout << (c1 - c2).val() << endl;
	return 0;
}
0