Submission #1269351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269351		PagodePaiva	Park (BOI16_park)	Pypy 3	0 / 100	145 ms	51116 KiB

park

import sys
import numpy as np
from scipy.spatial import Delaunay
from math import sqrt
class DSU:
    def __init__(self,n):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self,x):
        while self.p[x]!=x:
            self.p[x]=self.p[self.p[x]]
            x=self.p[x]
        return x
    def union(self,x,y):
        x=self.find(x); y=self.find(y)
        if x==y: return False
        if self.r[x]<self.r[y]:
            x,y=y,x
        self.p[y]=x
        if self.r[x]==self.r[y]:
            self.r[x]+=1
        return True
def main():
    data = sys.stdin
    line = data.readline().split()
    if not line: return
    N = int(line[0]); M = int(line[1])
    W,H = map(int,data.readline().split())
    xs = [0.0]*N; ys = [0.0]*N; rs = [0.0]*N
    for i in range(N):
        xi,yi,ri = data.readline().split()
        xs[i] = float(xi); ys[i] = float(yi); rs[i] = float(ri)
    pts = np.empty((N,2),dtype=float)
    pts[:,0]=xs; pts[:,1]=ys
    tri = Delaunay(pts)
    edges_set = set()
    for simplex in tri.simplices:
        a,b,c = simplex
        if a<b: edges_set.add((a,b))
        else: edges_set.add((b,a))
        if b<c: edges_set.add((b,c))
        else: edges_set.add((c,b))
        if c<a: edges_set.add((c,a))
        else: edges_set.add((a,c))
    WALL_L = N; WALL_R = N+1; WALL_B = N+2; WALL_T = N+3
    sensor_edges = []
    for i,j in edges_set:
        dx = xs[i]-xs[j]; dy = ys[i]-ys[j]
        d = sqrt(dx*dx + dy*dy)
        thr = (d - (rs[i] + rs[j]))/2.0
        if thr < 0.0: thr = 0.0
        sensor_edges.append((thr,i,j))
    edges_set.clear()
    wall_edges = []
    for i in range(N):
        thr = xs[i] - rs[i]
        if thr<0.0: thr=0.0
        wall_edges.append((thr,i,WALL_L))
        thr = (W - xs[i]) - rs[i]
        if thr<0.0: thr=0.0
        wall_edges.append((thr,i,WALL_R))
        thr = ys[i] - rs[i]
        if thr<0.0: thr=0.0
        wall_edges.append((thr,i,WALL_B))
        thr = (H - ys[i]) - rs[i]
        if thr<0.0: thr=0.0
        wall_edges.append((thr,i,WALL_T))
    sensor_edges.sort(key=lambda x: x[0])
    wall_edges.sort(key=lambda x: x[0])
    i_s = 0; n_s = len(sensor_edges)
    i_w = 0; n_w = len(wall_edges)
    dsu = DSU(N+4)
    thresholds = [None]*6
    count_remain = 6
    pair_u = [WALL_L, WALL_B, WALL_R, WALL_T, WALL_L, WALL_B]
    pair_v = [WALL_B, WALL_R, WALL_T, WALL_L, WALL_R, WALL_T]
    INF = float('inf')
    while (i_s < n_s or i_w < n_w) and count_remain>0:
        if i_s < n_s and (i_w>=n_w or sensor_edges[i_s][0] <= wall_edges[i_w][0]):
            thr,u,v = sensor_edges[i_s]; i_s+=1
        else:
            thr,u,v = wall_edges[i_w]; i_w+=1
        dsu.union(u,v)
        for k in range(6):
            if thresholds[k] is None:
                if dsu.find(pair_u[k]) == dsu.find(pair_v[k]):
                    thresholds[k] = thr
                    count_remain -= 1
    for k in range(6):
        if thresholds[k] is None:
            thresholds[k] = INF
    output = []
    for _ in range(M):
        R_str,e_str = data.readline().split()
        R = float(R_str); e = int(e_str)
        blb = R >= thresholds[0]
        bbr = R >= thresholds[1]
        brt = R >= thresholds[2]
        blt = R >= thresholds[3]
        blr = R >= thresholds[4]
        bbt = R >= thresholds[5]
        sealed = [False, blb, bbr, brt, blt]
        visited = [False]*5
        stack = [e]
        visited[e] = True
        while stack:
            u = stack.pop()
            for v in (1,2,3,4):
                if not visited[v]:
                    if sealed[u] or sealed[v]: continue
                    s = u+v
                    if bbt and s in (3,4,6,7): continue
                    if blr and s in (4,5,6): continue
                    visited[v] = True
                    stack.append(v)
        s = ''.join(str(c) for c in range(1,5) if visited[c])
        output.append(s)
    sys.stdout.write('\n'.join(output))

if __name__=="__main__":
    main()

Compilation message (stdout)

Compiling 'park.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42