結果

問題 No.1502 Many Simple Additions
ユーザー 沙耶花沙耶花
提出日時 2021-05-07 22:28:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 2,870 bytes
コンパイル時間 5,301 ms
コンパイル使用メモリ 282,912 KB
実行使用メモリ 21,932 KB
最終ジャッジ日時 2024-09-15 18:18:56
合計ジャッジ時間 7,588 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 67 ms
12,976 KB
testcase_28 AC 68 ms
13,228 KB
testcase_29 AC 28 ms
15,424 KB
testcase_30 AC 144 ms
21,932 KB
testcase_31 AC 142 ms
21,168 KB
testcase_32 AC 148 ms
21,292 KB
testcase_33 AC 75 ms
14,632 KB
testcase_34 AC 81 ms
15,132 KB
testcase_35 AC 79 ms
14,680 KB
testcase_36 AC 42 ms
11,392 KB
testcase_37 AC 41 ms
11,264 KB
testcase_38 AC 55 ms
12,948 KB
testcase_39 AC 31 ms
8,980 KB
testcase_40 AC 31 ms
7,748 KB
testcase_41 AC 12 ms
6,944 KB
testcase_42 AC 116 ms
18,488 KB
testcase_43 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:10:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   10 | vector<int> get_dis(auto &E){
      |                     ^~~~
main.cpp:31:30: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   31 | vector<long long> assign_all(auto &E,long long fir){
      |                              ^~~~
main.cpp:51:20: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   51 | long long get_diff(auto &E,vector<long long> v){
      |                    ^~~~

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000001

vector<int> get_dis(auto &E){
	vector<int> ret(E.size(),-1);
	queue<int> Q;
	Q.push(0);
	ret[0] = 0;
	
	while(Q.size()!=0){
		int u = Q.front();
		Q.pop();
		for(int i=0;i<E[u].size();i++){
			int v = E[u][i].first;
			if(ret[v]==-1){
				ret[v] = ret[u]^1;
				Q.push(v);
			}
		}
	}
	
	return ret;
}
 
vector<long long> assign_all(auto &E,long long fir){
	vector<long long> ret(E.size(),Inf);
	queue<int> Q;
	Q.push(0);
	ret[0] = fir;
	while(Q.size()!=0){
		int u = Q.front();
		Q.pop();
		for(int i=0;i<E[u].size();i++){
			int v = E[u][i].first;
			long long s = E[u][i].second;
			if(ret[v]==Inf){
				ret[v] = s - ret[u];
				Q.push(v);
			}
		}
	}
	return ret;
}
 
long long get_diff(auto &E,vector<long long> v){
	long long ret = 0;
	for(int i=0;i<E.size();i++){
		for(int j=0;j<E[i].size();j++){
			ret = max(ret,abs((v[i]+v[E[i][j].first])-E[i][j].second));
		}
	}
	return ret;
}

long long solve(int n,int m,vector<vector<pair<int,long long>>> E,long long K){
	if(n==1)return K;
	vector<int> parity = get_dis(E);
	
	bool is_bin = true;
	for(int i=0;i<n;i++){
		for(int j=0;j<E[i].size();j++){
			if(parity[i]==parity[E[i][j].first]){
				is_bin = false;
			}
		}
	}

	vector<long long> V = assign_all(E,1);
	
	if(is_bin){
		if(get_diff(E,V)!=0){
			return 0;
		}
		long long L = 0,R = K-1;
		for(int i=0;i<n;i++){
			if(parity[i]==0){
				L = max(L,1-V[i]);
				R = min(R,K-V[i]);
			}
			else{
				R = min(R,V[i]-1);
				L = max(L,V[i]-K);
			}
		}
		if(R<L)return 0;
		else return R-L+1;
	}
	else{
		long long t = get_diff(E,V);
		///cout<<t<<endl;
		V = assign_all(E,t/2+1LL);
		if(get_diff(E,V)!=0){
			return 0;
		}
		for(int i=0;i<n;i++){
			if(V[i]<=0){
				return 0;
			}
			if(V[i]>K){
				return 0;
			}
		}
		return 1;
	}
}

int main(){

	int N,M,K;
	cin>>N>>M>>K;
	
	vector<int> X(M),Y(M),Z(M);
	rep(i,M){
		scanf("%d %d %d",&X[i],&Y[i],&Z[i]);
		X[i]--;Y[i]--;
	}
	
	dsu D(N);
	rep(i,M){
		D.merge(X[i],Y[i]);
	}
	
	vector<vector<vector<pair<int,long long>>>> E;
	
	vector<pair<int,int>> par(N);
	{
		auto g = D.groups();
		E.resize(g.size());
		rep(i,g.size()){
			E[i].resize(g[i].size());
			rep(j,g[i].size()){
				par[g[i][j]] = make_pair(i,j);
			}
		}
	}
	
	rep(i,M){
		int ind = par[X[i]].first;
		int a = par[X[i]].second,b = par[Y[i]].second;
		
		E[ind][a].emplace_back(b,Z[i]);
		E[ind][b].emplace_back(a,Z[i]);
	}
	
	mint ans = 0;
	
	{
		mint temp = 1;
		rep(i,E.size()){
			temp *= solve(E[i].size(),0,E[i],K);
		}
		ans += temp;
	}
	//cout<<ans.val()<<endl;
	{
		mint temp = 1;
		rep(i,E.size()){
			temp *= solve(E[i].size(),0,E[i],K-1);
		}
		ans -= temp;
	}
	
	
	cout<<ans.val()<<endl;
	
		
    return 0;
}
0