結果

問題 No.1502 Many Simple Additions
コンテスト
ユーザー kotatsugame
提出日時 2021-05-07 22:08:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 2,382 bytes
コンパイル時間 1,199 ms
コンパイル使用メモリ 84,744 KB
実行使用メモリ 16,920 KB
最終ジャッジ日時 2024-09-15 18:17:54
合計ジャッジ時間 4,138 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main()
      | ^~~~
main.cpp: In function 'int main()':
main.cpp:67:36: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
   67 |                         if(fixed&&x!=nx)
      |                                   ~^~~~
main.cpp:57:27: note: 'x' was declared here
   57 |                 long long x;
      |                           ^

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint1000000007;
int N,M,K;
vector<pair<int,int> >G[1<<17];
bool vis[1<<17][2];
long A[1<<17][2];
vector<int>usd;
bool out;
void dfs(int u,int k)
{
	usd.push_back(u);
	for(pair<int,int>e:G[u])
	{
		int v=e.first;
		long nA=e.second-A[u][k];
		if(vis[v][!k])
		{
			if(A[v][!k]!=nA)out=true;
		}
		else
		{
			A[v][!k]=nA;
			vis[v][!k]=true;
			dfs(v,!k);
		}
	}
}
main()
{
	cin>>N>>M>>K;
	for(int i=0;i<M;i++)
	{
		int x,y,z;cin>>x>>y>>z;
		x--,y--;
		G[x].push_back(make_pair(y,z));
		G[y].push_back(make_pair(x,z));
	}
	mint ans=1,del=1;
	for(int i=0;i<N;i++)if(!vis[i][0]&&!vis[i][1])
	{
		vis[i][0]=true;
		A[i][0]=0;
		usd.clear();
		out=false;
		dfs(i,0);
		if(out)
		{
			cout<<0<<endl;
			return 0;
		}
		sort(usd.begin(),usd.end());
		usd.erase(unique(usd.begin(),usd.end()),usd.end());
		long long x;
		bool fixed=false;
		for(int u:usd)if(vis[u][0]&&vis[u][1])
		{
			if((A[u][1]-A[u][0])%2!=0)
			{
				cout<<0<<endl;
				return 0;
			}
			long long nx=(A[u][1]-A[u][0])/2;
			if(fixed&&x!=nx)
			{
				cout<<0<<endl;
				return 0;
			}
			fixed=true;
			x=nx;
		}
		if(fixed)
		{
			bool mx=false;
			for(int u:usd)
			{
				if(vis[u][0])
				{
					if(A[u][0]+x<1||K<A[u][0]+x)
					{
						cout<<0<<endl;
						return 0;
					}
					if(K==A[u][0]+x)mx=true;
				}
				if(vis[u][1])
				{
					if(A[u][1]-x<1||K<A[u][1]-x)
					{
						cout<<0<<endl;
						return 0;
					}
					if(K==A[u][1]-x)mx=true;
				}
			}
			if(mx)del=0;
		}
		else
		{
			long L=1,R=K;
			for(int u:usd)
			{
				if(vis[u][0])
				{
					L=max(L,1-A[u][0]);
					R=min(R,K-A[u][0]);
				}
				if(vis[u][1])
				{
					L=max(L,A[u][1]-K);
					R=min(R,A[u][1]-1);
				}
			}
			if(R<L)
			{
				cout<<0<<endl;
				return 0;
			}
			bool mxL=false,mxR=false;
			for(int u:usd)
			{
				if(vis[u][0])
				{
					if(A[u][0]+L==K)mxL=true;
					if(A[u][0]+R==K)mxR=true;
				}
				if(vis[u][1])
				{
					if(A[u][1]-L==K)mxL=true;
					if(A[u][1]-R==K)mxR=true;
				}
			}
			if(L==R)
			{
				if(mxL||mxR)del=0;
			}
			else if(L+1==R)
			{
				ans*=2;
				if(mxL&&mxR)del=0;
				else if(!mxL&&!mxR)del*=2;
			}
			else
			{
				ans*=R-L+1;
				if(mxL&&mxR)del*=R-L-1;
				else if(mxL||mxR)del*=R-L;
				else del*=R-L+1;
			}
		}
	}
	ans-=del;
	cout<<ans.val()<<endl;
}
0