結果

問題 No.1502 Many Simple Additions
ユーザー kotatsugamekotatsugame
提出日時 2021-05-07 22:08:21
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,382 bytes
コンパイル時間 915 ms
コンパイル使用メモリ 83,340 KB
実行使用メモリ 16,032 KB
最終ジャッジ日時 2023-10-13 22:33:04
合計ジャッジ時間 4,570 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,700 KB
testcase_01 AC 4 ms
6,668 KB
testcase_02 AC 3 ms
6,740 KB
testcase_03 AC 3 ms
6,668 KB
testcase_04 AC 3 ms
6,668 KB
testcase_05 AC 3 ms
6,664 KB
testcase_06 AC 3 ms
6,688 KB
testcase_07 AC 3 ms
6,924 KB
testcase_08 AC 3 ms
6,688 KB
testcase_09 AC 3 ms
6,704 KB
testcase_10 AC 3 ms
6,796 KB
testcase_11 AC 3 ms
6,692 KB
testcase_12 AC 4 ms
6,704 KB
testcase_13 AC 3 ms
6,668 KB
testcase_14 AC 3 ms
6,672 KB
testcase_15 AC 3 ms
6,664 KB
testcase_16 AC 3 ms
6,704 KB
testcase_17 AC 3 ms
6,764 KB
testcase_18 AC 3 ms
6,700 KB
testcase_19 AC 4 ms
6,704 KB
testcase_20 AC 3 ms
6,696 KB
testcase_21 AC 3 ms
6,768 KB
testcase_22 AC 3 ms
6,924 KB
testcase_23 AC 3 ms
6,664 KB
testcase_24 AC 3 ms
6,692 KB
testcase_25 AC 3 ms
6,872 KB
testcase_26 AC 3 ms
6,732 KB
testcase_27 AC 107 ms
11,700 KB
testcase_28 AC 107 ms
11,904 KB
testcase_29 AC 11 ms
8,248 KB
testcase_30 AC 167 ms
16,032 KB
testcase_31 AC 168 ms
15,944 KB
testcase_32 AC 167 ms
15,908 KB
testcase_33 AC 123 ms
12,480 KB
testcase_34 AC 126 ms
12,892 KB
testcase_35 AC 121 ms
12,744 KB
testcase_36 AC 83 ms
8,668 KB
testcase_37 AC 83 ms
8,712 KB
testcase_38 AC 96 ms
10,816 KB
testcase_39 AC 60 ms
8,368 KB
testcase_40 AC 25 ms
7,680 KB
testcase_41 AC 6 ms
6,992 KB
testcase_42 AC 117 ms
14,176 KB
testcase_43 AC 3 ms
6,732 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:32:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]
   32 | main()
      | ^~~~
main.cpp: 関数 ‘int main()’ 内:
main.cpp:67:36: 警告: ‘x’ may be used uninitialized [-Wmaybe-uninitialized]
   67 |                         if(fixed&&x!=nx)
      |                                   ~^~~~
main.cpp:57:27: 備考: ‘x’ はここで定義されています
   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