結果
問題 | No.168 ものさし |
ユーザー | vwxyz |
提出日時 | 2022-06-21 10:47:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,271 ms / 2,000 ms |
コード長 | 6,277 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 261,852 KB |
最終ジャッジ日時 | 2024-10-14 04:08:22 |
合計ジャッジ時間 | 8,811 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 222 ms
96,236 KB |
testcase_01 | AC | 43 ms
55,168 KB |
testcase_02 | AC | 44 ms
55,040 KB |
testcase_03 | AC | 44 ms
55,040 KB |
testcase_04 | AC | 44 ms
55,424 KB |
testcase_05 | AC | 44 ms
54,912 KB |
testcase_06 | AC | 55 ms
63,744 KB |
testcase_07 | AC | 44 ms
55,168 KB |
testcase_08 | AC | 43 ms
54,912 KB |
testcase_09 | AC | 86 ms
76,444 KB |
testcase_10 | AC | 104 ms
76,920 KB |
testcase_11 | AC | 289 ms
110,840 KB |
testcase_12 | AC | 910 ms
239,248 KB |
testcase_13 | AC | 1,246 ms
261,656 KB |
testcase_14 | AC | 1,271 ms
261,852 KB |
testcase_15 | AC | 49 ms
55,424 KB |
testcase_16 | AC | 95 ms
76,800 KB |
testcase_17 | AC | 103 ms
76,288 KB |
testcase_18 | AC | 117 ms
78,720 KB |
testcase_19 | AC | 654 ms
163,792 KB |
testcase_20 | AC | 696 ms
171,756 KB |
testcase_21 | AC | 706 ms
172,020 KB |
testcase_22 | AC | 702 ms
171,896 KB |
ソースコード
import sys readline=sys.stdin.readline from collections import defaultdict class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph: self.graph=graph else: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: x,y=tpl[:2] if self.weighted else tpl if uwd[x]==self.inf or uwd[y]==self.inf: continue if not uwd[x]%2^uwd[y]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def Bisect_Int(ok,ng,is_ok): while abs(ok-ng)>1: mid=(ok+ng)//2 if is_ok(mid): ok=mid else: ng=mid return ok N=int(readline()) X,Y=[],[] for _ in range(N): x,y=map(int,readline().split()) X.append(x) Y.append(y) def is_ok(x): graph=[[] for i in range(N)] for i in range(N): for j in range(i+1,N): if (X[i]-X[j])**2+(Y[i]-Y[j])**2<=100*x**2: graph[i].append(j) graph[j].append(i) G=Graph(N,graph=graph) return N-1 in G.SIV_DFS(0,linked_components=True) ans=Bisect_Int(15*10**8,0,is_ok)*10 print(ans)