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

提出ソース

結果

問題	No.1502 Many Simple Additions
ユーザー	startcpp
提出日時	2021-05-07 23:25:40
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	337 ms / 2,000 ms
コード長	4,886 bytes
コンパイル時間	1,190 ms
コンパイル使用メモリ	92,768 KB
実行使用メモリ	29,216 KB
最終ジャッジ日時	2024-09-15 18:24:16
合計ジャッジ時間	5,234 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 8,000 KB
testcase_01	AC	5 ms 8,000 KB
testcase_02	AC	4 ms 8,064 KB
testcase_03	AC	4 ms 7,880 KB
testcase_04	AC	5 ms 8,136 KB
testcase_05	AC	5 ms 8,064 KB
testcase_06	AC	5 ms 8,008 KB
testcase_07	AC	4 ms 8,008 KB
testcase_08	AC	4 ms 8,008 KB
testcase_09	AC	4 ms 8,004 KB
testcase_10	AC	4 ms 8,004 KB
testcase_11	AC	4 ms 8,004 KB
testcase_12	AC	5 ms 8,004 KB
testcase_13	AC	5 ms 8,004 KB
testcase_14	AC	5 ms 8,000 KB
testcase_15	AC	4 ms 8,136 KB
testcase_16	AC	5 ms 8,008 KB
testcase_17	AC	5 ms 8,008 KB
testcase_18	AC	4 ms 8,132 KB
testcase_19	AC	4 ms 8,132 KB
testcase_20	AC	4 ms 8,004 KB
testcase_21	AC	5 ms 8,000 KB
testcase_22	AC	5 ms 8,128 KB
testcase_23	AC	5 ms 8,004 KB
testcase_24	AC	5 ms 8,004 KB
testcase_25	AC	5 ms 8,008 KB
testcase_26	AC	5 ms 8,004 KB
testcase_27	AC	160 ms 27,532 KB
testcase_28	AC	160 ms 27,668 KB
testcase_29	AC	60 ms 25,956 KB
testcase_30	AC	326 ms 29,216 KB
testcase_31	AC	337 ms 29,128 KB
testcase_32	AC	332 ms 29,088 KB
testcase_33	AC	169 ms 16,732 KB
testcase_34	AC	173 ms 17,520 KB
testcase_35	AC	167 ms 16,956 KB
testcase_36	AC	94 ms 11,848 KB
testcase_37	AC	94 ms 11,672 KB
testcase_38	AC	114 ms 13,916 KB
testcase_39	AC	68 ms 11,080 KB
testcase_40	AC	64 ms 16,792 KB
testcase_41	AC	25 ms 13,212 KB
testcase_42	AC	182 ms 27,076 KB
testcase_43	AC	4 ms 8,064 KB

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

ソースコード

raw source code

//すぐ分かることとして、「K以下，K-1以下を解けば良い」「連結成分ごとに独立」「各連結成分では1頂点の値 x を決めたら芋づる式に決まる（自由度1以下)」
//というのがある。x + num[0][i], -x + num[1][i] の形を各頂点iで覚えておき、同符号で異なる定数項が来たらダメ、異符号の項が来たら一意なので判定、
//そうでもなければxの範囲を求めて、という感じでやればよい。
//ここまでは分かるが、難しいのは細かい実装パート。
//x + a --- edge ---  -x + ? のとき、? = edge - a
//-x + a -- edge ---   x + ? のとき、? = edge - a
//そんなに難しくなかったの巻。
//異符号の項が来た場合、
//・x + a = -x + b ⇔ 2x = b - a ⇔ x = (b - a) / 2．aとbの偶奇が違ったり、b - aが負だったらダメ。
//値の範囲制約 (K以下の問題を解く場合）
//・xは整数
//・0 <= x <= K
//・x + a >= 1 : x >= -a + 1
//・x + a <= K : x <= K - a
//・-x + b >= 1 : x <= b - 1
//・-x + b <= K : x >= b - K
//これらでxの範囲を絞って、判定すればおっけー。
//全て同符号しかなく各頂点矛盾しないなら、単純にmax >= minか判定して、max - min + 1通り。
//
//最初の連結成分分けるパートはatcoder/dsuを使えばすぐだが、せっかく線形で解ける問題なので、真面目に幅優先していきます。
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n, m;
vector<int> et[100000];
vector<int> ec[100000];

vector<vector<int>> make_groups() {
	int i;
	queue<int> que;
	vector<bool> used(n, false);
	vector<vector<int>> groups;
	
	rep(i, n) {
		if (used[i]) continue;
		
		vector<int> group;
		used[i] = true;
		que.push(i);
		group.push_back(i);
		
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (int j = 0; j < et[v].size(); j++) {
				int nv = et[v][j];
				if (used[nv] == false) {
					used[nv] = true;
					que.push(nv);
					group.push_back(nv);
				}
			}
		}
		groups.push_back(group);
	}
	return groups;
}

const int mod = 1000000007;

//groupsは連結成分, x + nums[i][0], -x + nums[i][1], used[i][0, 1] : visit flag を頂点iについて持つ
int count_array_group(int K, vector<int> &group, vector<vector<int>> &nums, vector<vector<bool>> &used) {
	int s = group[0];
	typedef pair<int, int> P; //(i, 0(+) or 1(-))
	queue<P> que;
	
	//始点を x とおく
	used[s][0] = true;
	nums[s][0] = 0;
	que.push(P(s, 0));
	
	while (!que.empty()) {
		P now = que.front(); que.pop();
		int v = now.first;
		int f = now.second;
		
		for (int i = 0; i < et[v].size(); i++) {
			int nv = et[v][i];
			int nf = !f;
			int next_num = ec[v][i] - nums[v][f];
			
			//同符号の矛盾を弾く
			if (used[nv][nf] == true && nums[nv][nf] != next_num) {
				return 0;
			}
			if (!used[nv][nf]) {
				used[nv][nf] = true;
				nums[nv][nf] = next_num;
				que.push(P(nv, nf));
			}
		}
	}
	
	//集計
	int xlow = 1;
	int xhigh = K;
	
	for (int i = 0; i < group.size(); i++) {
		int v = group[i];
		int a = nums[v][0];
		int b = nums[v][1];
		
		//cerr << v + 1;
		//if (used[v][0]) cerr << ", x + " << a;
		//if (used[v][1]) cerr << ", -x + " << b;
		//cerr << endl;
	}
	
	for (int i = 0; i < group.size(); i++) {
		int v = group[i];
		int a = nums[v][0];
		int b = nums[v][1];
		
		if (used[v][0] && used[v][1]) {
			if (b - a < 0 || (b - a) % 2 != 0) {
				//cerr << "v = " << v + 1 << ", break1" << endl;
				return 0;
			}
			xlow = max(xlow, (b - a) / 2);
			xhigh = min(xhigh, (b - a) / 2);
		}
		if (used[v][0]) {
			xlow = max(xlow, -a + 1);
			xhigh = min(xhigh, K - a);
		}
		if (used[v][1]) {
			xlow = max(xlow, b - K);
			xhigh = min(xhigh, b - 1);
		}
		//cerr << "xlow = " << xlow << ", " << " xhigh = " << xhigh << endl;
	}
	
	if (xlow > xhigh) return 0;
	return xhigh - xlow + 1;
}

//max A <= Kのとき、何通り？
int count_array(int K, vector<vector<int>> &groups) {
	int i;
	int ret = 1;
	
	vector<vector<int>> nums(n, vector<int>(2));
	vector<vector<bool>> used(n, vector<bool>(2, false));
	
	//cerr << "K = " << K << endl;
	rep(i, groups.size()) {
		int res = count_array_group(K, groups[i], nums, used);
		ret *= res;
		ret %= mod;
		
		/*for (int j = 0; j < groups[i].size(); j++) {
			cerr << groups[i][j] + 1 << " ";
		}*/
		//cerr << ", res = " << res << endl;
		//cerr << endl;
	}
	return ret;
}

signed main() {
	int i, K;
	
	cin >> n >> m >> K;
	rep(i, m) {
		int x, y, z;
		cin >> x >> y >> z;
		x--; y--;
		et[x].push_back(y);
		et[y].push_back(x);
		ec[x].push_back(z);
		ec[y].push_back(z);
	}
	
	vector<vector<int>> groups = make_groups();
	int ans = (count_array(K, groups) - count_array(K - 1, groups) + mod) % mod;
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード