結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-19 15:21:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 686 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 87,028 KB |
実行使用メモリ | 121,700 KB |
最終ジャッジ日時 | 2023-09-12 01:39:43 |
合計ジャッジ時間 | 30,801 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
71,716 KB |
testcase_01 | AC | 90 ms
71,560 KB |
testcase_02 | AC | 91 ms
71,672 KB |
testcase_03 | AC | 92 ms
71,820 KB |
testcase_04 | AC | 260 ms
117,680 KB |
testcase_05 | AC | 282 ms
115,820 KB |
testcase_06 | AC | 93 ms
71,784 KB |
testcase_07 | AC | 91 ms
71,676 KB |
testcase_08 | AC | 91 ms
71,472 KB |
testcase_09 | AC | 92 ms
71,664 KB |
testcase_10 | AC | 464 ms
102,796 KB |
testcase_11 | AC | 427 ms
98,624 KB |
testcase_12 | AC | 391 ms
97,396 KB |
testcase_13 | AC | 580 ms
115,500 KB |
testcase_14 | AC | 609 ms
116,640 KB |
testcase_15 | AC | 335 ms
92,352 KB |
testcase_16 | AC | 373 ms
93,864 KB |
testcase_17 | AC | 515 ms
107,816 KB |
testcase_18 | AC | 228 ms
82,308 KB |
testcase_19 | AC | 399 ms
96,972 KB |
testcase_20 | AC | 447 ms
101,468 KB |
testcase_21 | AC | 411 ms
97,864 KB |
testcase_22 | AC | 210 ms
80,820 KB |
testcase_23 | AC | 479 ms
104,788 KB |
testcase_24 | AC | 289 ms
87,084 KB |
testcase_25 | AC | 402 ms
97,780 KB |
testcase_26 | AC | 503 ms
105,900 KB |
testcase_27 | AC | 335 ms
91,784 KB |
testcase_28 | AC | 583 ms
114,000 KB |
testcase_29 | AC | 484 ms
107,752 KB |
testcase_30 | AC | 270 ms
84,492 KB |
testcase_31 | AC | 614 ms
119,116 KB |
testcase_32 | AC | 585 ms
115,080 KB |
testcase_33 | AC | 465 ms
103,404 KB |
testcase_34 | AC | 464 ms
108,088 KB |
testcase_35 | AC | 403 ms
101,616 KB |
testcase_36 | AC | 276 ms
84,792 KB |
testcase_37 | AC | 280 ms
86,424 KB |
testcase_38 | AC | 516 ms
114,304 KB |
testcase_39 | AC | 385 ms
93,848 KB |
testcase_40 | AC | 367 ms
93,544 KB |
testcase_41 | AC | 505 ms
110,476 KB |
testcase_42 | AC | 404 ms
95,392 KB |
testcase_43 | AC | 389 ms
98,600 KB |
testcase_44 | AC | 409 ms
96,712 KB |
testcase_45 | AC | 342 ms
93,140 KB |
testcase_46 | AC | 271 ms
84,776 KB |
testcase_47 | AC | 247 ms
82,956 KB |
testcase_48 | AC | 520 ms
116,312 KB |
testcase_49 | AC | 208 ms
81,712 KB |
testcase_50 | AC | 92 ms
71,688 KB |
testcase_51 | AC | 93 ms
71,532 KB |
testcase_52 | AC | 659 ms
118,500 KB |
testcase_53 | AC | 686 ms
121,700 KB |
07_evil_01.txt | AC | 1,122 ms
162,816 KB |
07_evil_02.txt | AC | 1,556 ms
199,368 KB |
ソースコード
class dsu: def __init__(self,n): assert n>0,"n must be Natural" self.n=n self.parents=[-1]*n return def find(self,x): assert x<self.n,"warning!! this is 0 index" if self.parents[x]<0: return x self.parents[x]=self.find(self.parents[x]) return self.parents[x] def merge(self,x,y): assert x<self.n and y<self.n,"warning!! this is 0 index" 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 return def size(self,x): assert x<self.n,"warning!! this is 0 index" return -self.parents[self.find(x)] def same(self,x,y): assert x<self.n and y<self.n,"warning!! this is 0 index" return self.find(x)==self.find(y) def leader(self,x): assert x<self.n,"warning!! this is 0 index" if self.parents[x]<0: return x self.parents[x]=self.leader(self.parents[x]) return self.parents[x] def groups(self): ld=[self.leader(i) for i in range(self.n)] res=[[] for _ in range(self.n)] for i in range(self.n): res[ld[i]].append(i) return list(filter(lambda a:a !=[],res)) from collections import deque def main(): N=int(input()) uf=dsu(N) to=[[]for _ in[0]*N] for i in range(N): A,B=map(int,input().split()) uf.merge(A-1,B-1) to[A-1].append([B-1,i]) if A!=B: to[B-1].append([A-1,i]) seen=[0]*N ans=[-1]*N gr=uf.groups() for linked in gr: is_cycle=True root=-1 cycle_cnt=0 for point in linked: link_size=len(to[point]) for k in range(link_size): if to[point][k][0]==point: cycle_cnt+=1 is_cycle=False ans[to[point][k][1]]=point+1 root=point if cycle_cnt>1: print("No") return if is_cycle: next_point=-1 que=deque() que.append([linked[0],-1]) while que: q=que.pop() for j in to[q[0]]: if j[1]==q[1]: continue if seen[j[0]]: root=j[0] next_point=q[0] ans[j[1]]=root+1 que.clear() break que.append([j[0],j[1]]) seen[q[0]]=1 if next_point==-1: print("No") return dq=deque() dq.append(root) while dq: q=dq.pop() for j in to[q]: if ans[j[1]]==-1: ans[j[1]]=j[0]+1 dq.append(j[0]) for i in ans: if i==-1: print("No") return print("Yes") for i in ans: print(i) return main()