結果

問題 No.1502 Many Simple Additions
コンテスト
ユーザー 沙耶花
提出日時 2021-05-07 22:28:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 2,870 bytes
コンパイル時間 4,603 ms
コンパイル使用メモリ 271,244 KB
最終ジャッジ日時 2025-01-21 08:25:08
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
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){
      |                    ^~~~
main.cpp: In function ‘int main()’:
main.cpp:120:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  120 |                 scanf("%d %d %d",&X[i],&Y[i],&Z[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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