結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-12 20:15:22 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,186 ms / 2,000 ms |
コード長 | 3,995 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 11,344 KB |
実行使用メモリ | 72,204 KB |
最終ジャッジ日時 | 2023-09-12 01:29:12 |
合計ジャッジ時間 | 36,834 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
13,352 KB |
testcase_01 | AC | 21 ms
9,064 KB |
testcase_02 | AC | 21 ms
8,968 KB |
testcase_03 | AC | 21 ms
8,984 KB |
testcase_04 | AC | 477 ms
67,728 KB |
testcase_05 | AC | 593 ms
72,204 KB |
testcase_06 | AC | 21 ms
9,044 KB |
testcase_07 | AC | 21 ms
8,992 KB |
testcase_08 | AC | 21 ms
9,104 KB |
testcase_09 | AC | 21 ms
9,052 KB |
testcase_10 | AC | 590 ms
47,320 KB |
testcase_11 | AC | 497 ms
40,204 KB |
testcase_12 | AC | 382 ms
36,532 KB |
testcase_13 | AC | 972 ms
66,180 KB |
testcase_14 | AC | 989 ms
65,312 KB |
testcase_15 | AC | 283 ms
28,796 KB |
testcase_16 | AC | 335 ms
32,604 KB |
testcase_17 | AC | 802 ms
56,092 KB |
testcase_18 | AC | 61 ms
13,284 KB |
testcase_19 | AC | 390 ms
35,684 KB |
testcase_20 | AC | 583 ms
45,548 KB |
testcase_21 | AC | 473 ms
38,936 KB |
testcase_22 | AC | 47 ms
11,992 KB |
testcase_23 | AC | 608 ms
48,068 KB |
testcase_24 | AC | 146 ms
19,672 KB |
testcase_25 | AC | 381 ms
37,212 KB |
testcase_26 | AC | 705 ms
52,832 KB |
testcase_27 | AC | 269 ms
27,788 KB |
testcase_28 | AC | 935 ms
62,656 KB |
testcase_29 | AC | 653 ms
51,544 KB |
testcase_30 | AC | 113 ms
18,324 KB |
testcase_31 | AC | 1,092 ms
71,044 KB |
testcase_32 | AC | 889 ms
63,324 KB |
testcase_33 | AC | 535 ms
46,272 KB |
testcase_34 | AC | 554 ms
54,796 KB |
testcase_35 | AC | 385 ms
45,612 KB |
testcase_36 | AC | 96 ms
18,040 KB |
testcase_37 | AC | 116 ms
21,892 KB |
testcase_38 | AC | 661 ms
65,544 KB |
testcase_39 | AC | 316 ms
33,532 KB |
testcase_40 | AC | 260 ms
33,664 KB |
testcase_41 | AC | 689 ms
56,676 KB |
testcase_42 | AC | 399 ms
37,412 KB |
testcase_43 | AC | 311 ms
38,160 KB |
testcase_44 | AC | 410 ms
38,316 KB |
testcase_45 | AC | 209 ms
30,544 KB |
testcase_46 | AC | 99 ms
19,336 KB |
testcase_47 | AC | 81 ms
15,472 KB |
testcase_48 | AC | 675 ms
66,456 KB |
testcase_49 | AC | 44 ms
11,900 KB |
testcase_50 | AC | 21 ms
9,156 KB |
testcase_51 | AC | 21 ms
9,016 KB |
testcase_52 | AC | 1,180 ms
72,184 KB |
testcase_53 | AC | 1,186 ms
72,176 KB |
07_evil_01.txt | TLE | - |
07_evil_02.txt | TLE | - |
ソースコード
class INPUT: def __init__(self): self._l=open(0).read().split() self._length=len(self._l) self._index=0 return def stream(self,k=1,f=int,f2=False): assert(-1<k) if self._length==self._index or self._length-self._index<k: raise Exception("There is no input!") elif f!=str: if k==0: ret=list(map(f,self._l[self._index:])) self._index=self._length return ret if k==1 and not f2: ret=f(self._l[self._index]) self._index+=1 return ret if k==1 and f2: ret=[f(self._l[self._index])] self._index+=1 return ret ret=[] for _ in [0]*k: ret.append(f(self._l[self._index])) self._index+=1 return ret else: if k==0: ret=list(self._l[self._index:]) self._index=self._length return ret if k==1 and not f2: ret=self._l[self._index] self._index+=1 return ret if k==1 and f2: ret=[self._l[self._index]] self._index+=1 return ret ret=[] for _ in [0]*k: ret.append(self._l[self._index]) self._index+=1 return ret pin=INPUT().stream """ pin(number[default:1],f[default:int],f2[default:False]) if number==0 -> return left all listを変数で受け取るとき、必ずlistをTrueにすること。 """ 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=pin(1) uf=dsu(N) to=[[]for _ in[0]*N] for i in range(N): A,B=pin(2) 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()