結果
| 問題 |
No.1023 Cyclic Tour
|
| コンテスト | |
| ユーザー |
 vwxyz
|
| 提出日時 | 2024-07-17 04:25:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 513 ms / 2,000 ms |
| コード長 | 5,961 bytes |
| コンパイル時間 | 238 ms |
| コンパイル使用メモリ | 82,428 KB |
| 実行使用メモリ | 122,908 KB |
| 最終ジャッジ日時 | 2024-07-17 04:25:33 |
| 合計ジャッジ時間 | 20,965 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 49 |
ソースコード
from collections import defaultdict
class UnionFind:
def __init__(self,N,label=None,f=None,weighted=False,rollback=False):
self.N=N
self.parents=[None]*self.N
self.size=[1]*self.N
self.roots={i for i in range(self.N)}
self.label=label
if self.label!=None:
self.label=[x for x in label]
self.f=f
self.weighted=weighted
if self.weighted:
self.weight=[0]*self.N
self.rollback=rollback
if self.rollback:
self.operate_list=[]
self.operate_set=[]
def Find(self,x):
stack=[]
while self.parents[x]!=None:
stack.append(x)
x=self.parents[x]
if not self.rollback:
if self.weighted:
w=0
for y in stack[::-1]:
self.parents[y]=x
w+=self.weight[y]
self.weight[y]=w
else:
for y in stack[::-1]:
self.parents[y]=x
return x
def Union(self,x,y,w=None):
root_x=self.Find(x)
root_y=self.Find(y)
if self.rollback:
self.operate_list.append([])
self.operate_set.append([])
if root_x==root_y:
if self.weighted:
if self.weight[y]-self.weight[x]==w:
return True
else:
return False
else:
if self.size[root_x]<self.size[root_y]:
x,y=y,x
root_x,root_y=root_y,root_x
if self.weighted:
w=-w
if self.rollback:
self.operate_list[-1].append((self.parents,root_y,self.parents[root_y]))
self.operate_list[-1].append((self.size,root_x,self.size[root_x]))
self.operate_set[-1].append(root_y)
if self.label!=None:
self.operate_list[-1]((self.label,root_x,self.label[root_x]))
if self.weighted:
self.operate_list[-1].append((self.weight,root_y,self.weight[root_y]))
self.parents[root_y]=root_x
self.size[root_x]+=self.size[root_y]
self.roots.remove(root_y)
if self.label!=None:
self.label[root_x]=self.f(self.label[root_x],self.label[root_y])
if self.weighted:
self.weight[root_y]=w+self.weight[x]-self.weight[y]
def Size(self,x):
return self.size[self.Find(x)]
def Same(self,x,y):
return self.Find(x)==self.Find(y)
def Label(self,x):
return self.label[self.Find(x)]
def Weight(self,x,y):
root_x=self.Find(x)
root_y=self.Find(y)
if root_x!=root_y:
return None
return self.weight[y]-self.weight[x]
def Roots(self):
return list(self.roots)
def Linked_Components_Count(self):
return len(self.roots)
def Linked_Components(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return linked_components
def Rollback(self):
assert self.rollback
if self.operate_list:
for lst,x,v in self.operate_list.pop():
lst[x]=v
for x in self.operate_set.pop():
self.roots.add(x)
return True
else:
return False
def __str__(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return "\n".join(f"{r}: {linked_components[r]}" for r in sorted(list(linked_components.keys())))
def SCC(N,edges):
start = [0] * (N + 1)
elist = [0] * len(edges)
for e in edges:
start[e[0] + 1] += 1
for i in range(1, N + 1):
start[i] += start[i - 1]
counter = start[:]
for e in edges:
elist[counter[e[0]]] = e[1]
counter[e[0]] += 1
N = N
now_ord = group_num = 0
visited = []
low = [0] * N
order = [-1] * N
ids = [0] * N
parent = [-1] * N
stack = []
for i in range(N):
if order[i] == -1:
stack.append(i)
stack.append(i)
while stack:
v = stack.pop()
if order[v] == -1:
low[v] = order[v] = now_ord
now_ord += 1
visited.append(v)
for i in range(start[v], start[v + 1]):
to = elist[i]
if order[to] == -1:
stack.append(to)
stack.append(to)
parent[to] = v
else:
low[v] = min(low[v], order[to])
else:
if low[v] == order[v]:
while True:
u = visited.pop()
order[u] = N
ids[u] = group_num
if u == v:
break
group_num += 1
if parent[v] != -1:
low[parent[v]] = min(low[parent[v]], low[v])
for i, x in enumerate(ids):
ids[i] = group_num - 1 - x
groups = [[] for _ in range(group_num)]
for i, x in enumerate(ids):
groups[x].append(i)
return groups
N,M=map(int,input().split())
AB=[[],[]]
for m in range(M):
a,b,c=map(int,input().split())
a-=1;b-=1;c-=1
AB[c].append((a,b))
UF=UnionFind(N)
ans="No"
for a,b in AB[0]:
if UF.Same(a,b):
ans="Yes"
UF.Union(a,b)
edges=[]
for a,b in AB[1]:
a=UF.Find(a)
b=UF.Find(b)
if a==b:
ans="Yes"
edges.append((a,b))
scc=SCC(N,edges=edges)
for lc in scc:
if len(lc)>=2:
ans="Yes"
print(ans)