結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-17 13:52:43 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,090 ms / 2,000 ms |
コード長 | 2,754 bytes |
コンパイル時間 | 488 ms |
コンパイル使用メモリ | 11,296 KB |
実行使用メモリ | 58,060 KB |
最終ジャッジ日時 | 2023-09-12 01:35:47 |
合計ジャッジ時間 | 26,839 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
8,880 KB |
testcase_01 | AC | 20 ms
8,916 KB |
testcase_02 | AC | 19 ms
9,044 KB |
testcase_03 | AC | 19 ms
9,028 KB |
testcase_04 | AC | 406 ms
53,648 KB |
testcase_05 | AC | 510 ms
58,048 KB |
testcase_06 | AC | 20 ms
8,868 KB |
testcase_07 | AC | 20 ms
8,960 KB |
testcase_08 | AC | 20 ms
8,912 KB |
testcase_09 | AC | 19 ms
9,040 KB |
testcase_10 | AC | 515 ms
37,904 KB |
testcase_11 | AC | 410 ms
32,864 KB |
testcase_12 | AC | 312 ms
29,764 KB |
testcase_13 | AC | 856 ms
53,184 KB |
testcase_14 | AC | 902 ms
52,552 KB |
testcase_15 | AC | 240 ms
24,192 KB |
testcase_16 | AC | 293 ms
27,432 KB |
testcase_17 | AC | 724 ms
45,984 KB |
testcase_18 | AC | 55 ms
12,124 KB |
testcase_19 | AC | 344 ms
30,016 KB |
testcase_20 | AC | 524 ms
36,964 KB |
testcase_21 | AC | 422 ms
31,872 KB |
testcase_22 | AC | 42 ms
11,056 KB |
testcase_23 | AC | 526 ms
39,088 KB |
testcase_24 | AC | 114 ms
17,256 KB |
testcase_25 | AC | 328 ms
30,224 KB |
testcase_26 | AC | 616 ms
42,484 KB |
testcase_27 | AC | 211 ms
23,372 KB |
testcase_28 | AC | 790 ms
50,772 KB |
testcase_29 | AC | 554 ms
42,744 KB |
testcase_30 | AC | 86 ms
16,068 KB |
testcase_31 | AC | 967 ms
56,940 KB |
testcase_32 | AC | 807 ms
50,868 KB |
testcase_33 | AC | 476 ms
38,052 KB |
testcase_34 | AC | 487 ms
44,500 KB |
testcase_35 | AC | 307 ms
37,604 KB |
testcase_36 | AC | 75 ms
16,332 KB |
testcase_37 | AC | 92 ms
18,672 KB |
testcase_38 | AC | 609 ms
52,940 KB |
testcase_39 | AC | 240 ms
27,736 KB |
testcase_40 | AC | 213 ms
27,816 KB |
testcase_41 | AC | 586 ms
45,876 KB |
testcase_42 | AC | 317 ms
30,848 KB |
testcase_43 | AC | 247 ms
31,524 KB |
testcase_44 | AC | 348 ms
31,032 KB |
testcase_45 | AC | 168 ms
25,680 KB |
testcase_46 | AC | 85 ms
16,932 KB |
testcase_47 | AC | 66 ms
13,952 KB |
testcase_48 | AC | 564 ms
53,920 KB |
testcase_49 | AC | 38 ms
11,072 KB |
testcase_50 | AC | 19 ms
8,948 KB |
testcase_51 | AC | 20 ms
8,876 KB |
testcase_52 | AC | 1,090 ms
58,044 KB |
testcase_53 | AC | 1,075 ms
58,060 KB |
07_evil_01.txt | RE | - |
07_evil_02.txt | RE | - |
ソースコード
#行数assert 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 sys import stdin pin=stdin.readline from collections import deque def main(): N=int(pin()) assert(1<=N<=10**5) uf=dsu(N) to=[[]for _ in[0]*N] for i in range(N): A,B=map(int,pin().split()) 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]) 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()