結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-16 23:57:26 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,017 ms / 2,000 ms |
コード長 | 4,172 bytes |
コンパイル時間 | 493 ms |
コンパイル使用メモリ | 11,216 KB |
実行使用メモリ | 72,260 KB |
最終ジャッジ日時 | 2023-09-12 01:33:04 |
合計ジャッジ時間 | 26,747 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
8,984 KB |
testcase_01 | AC | 20 ms
8,940 KB |
testcase_02 | AC | 20 ms
9,028 KB |
testcase_03 | AC | 20 ms
9,080 KB |
testcase_04 | AC | 459 ms
67,760 KB |
testcase_05 | AC | 570 ms
72,060 KB |
testcase_06 | AC | 21 ms
8,944 KB |
testcase_07 | AC | 20 ms
9,024 KB |
testcase_08 | AC | 20 ms
8,940 KB |
testcase_09 | AC | 21 ms
8,944 KB |
testcase_10 | AC | 508 ms
47,064 KB |
testcase_11 | AC | 415 ms
39,932 KB |
testcase_12 | AC | 317 ms
35,728 KB |
testcase_13 | AC | 835 ms
66,444 KB |
testcase_14 | AC | 891 ms
65,112 KB |
testcase_15 | AC | 248 ms
28,984 KB |
testcase_16 | AC | 278 ms
33,124 KB |
testcase_17 | AC | 704 ms
55,996 KB |
testcase_18 | AC | 56 ms
13,224 KB |
testcase_19 | AC | 331 ms
35,664 KB |
testcase_20 | AC | 488 ms
45,216 KB |
testcase_21 | AC | 409 ms
38,296 KB |
testcase_22 | AC | 44 ms
11,988 KB |
testcase_23 | AC | 498 ms
47,980 KB |
testcase_24 | AC | 118 ms
19,660 KB |
testcase_25 | AC | 323 ms
36,832 KB |
testcase_26 | AC | 584 ms
52,484 KB |
testcase_27 | AC | 227 ms
27,924 KB |
testcase_28 | AC | 804 ms
62,808 KB |
testcase_29 | AC | 541 ms
51,276 KB |
testcase_30 | AC | 95 ms
18,332 KB |
testcase_31 | AC | 936 ms
70,924 KB |
testcase_32 | AC | 724 ms
62,900 KB |
testcase_33 | AC | 424 ms
46,128 KB |
testcase_34 | AC | 471 ms
54,508 KB |
testcase_35 | AC | 326 ms
45,864 KB |
testcase_36 | AC | 83 ms
18,180 KB |
testcase_37 | AC | 100 ms
21,740 KB |
testcase_38 | AC | 560 ms
65,632 KB |
testcase_39 | AC | 251 ms
33,796 KB |
testcase_40 | AC | 226 ms
33,516 KB |
testcase_41 | AC | 566 ms
56,484 KB |
testcase_42 | AC | 319 ms
37,192 KB |
testcase_43 | AC | 252 ms
38,040 KB |
testcase_44 | AC | 325 ms
37,876 KB |
testcase_45 | AC | 174 ms
30,596 KB |
testcase_46 | AC | 87 ms
19,356 KB |
testcase_47 | AC | 69 ms
15,364 KB |
testcase_48 | AC | 575 ms
66,792 KB |
testcase_49 | AC | 40 ms
11,780 KB |
testcase_50 | AC | 20 ms
9,000 KB |
testcase_51 | AC | 20 ms
9,080 KB |
testcase_52 | AC | 1,017 ms
72,260 KB |
testcase_53 | AC | 1,015 ms
72,176 KB |
07_evil_01.txt | RE | - |
07_evil_02.txt | RE | - |
ソースコード
#assert 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) assert(1<=N<=10**5) uf=dsu(N) to=[[]for _ in[0]*N] for i in range(N): A,B=pin(2) assert(1<=A<=N) assert(1<=B<=N) uf.merge(A-1,B-1) to[A-1].append([B-1,i]) if A!=B: to[B-1].append([A-1,i]) is_input=False try: pin(0) is_input=True except: pass if is_input: raise Exception 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()