#1004583 (PyPy3) No.2860 Heal Slimes

提出ソース

結果

問題	No.2860 Heal Slimes
ユーザー	shobonvip
提出日時	2024-08-25 14:39:34
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	1,145 bytes
コンパイル時間	185 ms
コンパイル使用メモリ	82,540 KB
実行使用メモリ	109,376 KB
最終ジャッジ日時	2024-08-25 14:39:46
合計ジャッジ時間	12,348 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	114 ms 77,028 KB
testcase_11	AC	115 ms 77,156 KB
testcase_12	AC	117 ms 76,876 KB
testcase_13	AC	125 ms 77,180 KB
testcase_14	AC	115 ms 77,060 KB
testcase_15	AC	118 ms 76,844 KB
testcase_16	AC	119 ms 76,996 KB
testcase_17	AC	124 ms 76,728 KB
testcase_18	AC	121 ms 77,024 KB
testcase_19	AC	117 ms 76,824 KB
testcase_20	AC	96 ms 103,408 KB
testcase_21	AC	106 ms 103,332 KB
testcase_22	AC	95 ms 92,220 KB
testcase_23	AC	113 ms 102,424 KB
testcase_24	AC	113 ms 100,128 KB
testcase_25	AC	102 ms 98,892 KB
testcase_26	AC	89 ms 90,236 KB
testcase_27	AC	118 ms 102,884 KB
testcase_28	AC	116 ms 100,268 KB
testcase_29	AC	103 ms 99,820 KB
testcase_30	AC	116 ms 109,296 KB
testcase_31	AC	113 ms 102,212 KB
testcase_32	AC	124 ms 103,960 KB
testcase_33	AC	115 ms 109,376 KB
testcase_34	AC	122 ms 103,064 KB
testcase_35	AC	115 ms 106,800 KB
testcase_36	AC	113 ms 109,304 KB
testcase_37	AC	112 ms 106,996 KB
testcase_38	AC	117 ms 109,336 KB
testcase_39	AC	117 ms 106,560 KB
testcase_40	AC	125 ms 103,716 KB
testcase_41	AC	121 ms 102,820 KB
testcase_42	AC	122 ms 102,780 KB
testcase_43	AC	124 ms 105,384 KB
testcase_44	AC	123 ms 102,792 KB
testcase_45	AC	116 ms 102,568 KB
testcase_46	AC	129 ms 102,680 KB
testcase_47	AC	113 ms 102,824 KB
testcase_48	AC	120 ms 102,824 KB
testcase_49	AC	111 ms 102,940 KB
testcase_50	AC	127 ms 105,756 KB
testcase_51	AC	120 ms 102,676 KB
testcase_52	AC	122 ms 102,692 KB
testcase_53	AC	113 ms 102,832 KB
testcase_54	AC	128 ms 105,140 KB
testcase_55	AC	115 ms 102,676 KB
testcase_56	AC	127 ms 106,028 KB
testcase_57	AC	127 ms 104,104 KB
testcase_58	AC	122 ms 102,928 KB
testcase_59	AC	112 ms 102,688 KB

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

ソースコード

raw source code

from collections import defaultdict

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]
	
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			x, y = y, x
		self.parents[x] += self.parents[y]
		self.parents[y] = x

def solve():
	n, k, x = map(int,input().split())
	h = list(map(int,input().split()))
	if k == n:
		if max(h) == min(h):
			print("Yes")
		else:
			print("No")
		return 

	v = [h[i+1] - h[i] for i in range(n-1)]
	uf = UnionFind(n)
	for i in range(n-k+1):
		# h[i], ...,  h[i+k-1]
		if i == 0:
			uf.union(i+k-1, n-1)			
		elif i == n-k:
			uf.union(i-1, n-1)
		else:
			uf.union(i-1, i+k-1)
	
	dr = 0
	t = defaultdict(int)
	for i in range(n-1):
		if uf.find(n-1) == uf.find(i):
			dr += v[i]
		else:
			t[uf.find(i)] += v[i]
	if dr % x != 0:
		print("No")
		return
	for i,c in t.items():
		if c != 0:
			print("No")
			return
	print("Yes")

t = int(input())
for _ in range(t):
	solve()

yukicoder

結果

テストケース

ソースコード