Problem:


Score: 600 points

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.

Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

if U_i is U, it flies in the positive y direction;

if U_i is R, it flies in the positive x direction;

if U_i is D, it flies in the negative y direction;

if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.

If there is such a pair, find the number of seconds after which the first collision will happen.

We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

1 \leq N \leq 200000

0 \leq X_i, Y_i \leq 200000

U_i is U, R, D, or L.

The current positions of the N airplanes, (X_i, Y_i), are all distinct.

N, X_i, and Y_i are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 U_1
X_2 Y_2 U_2
X_3 Y_3 U_3
:
X_N Y_N U_N

Output

If there is a pair of airplanes that will collide with each other if they keep flying as they are now, print an integer representing the number of seconds after which the first collision will happen.

If there is no such pair, print SAFE.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.  

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100



Sample input:
2
11 1 U
11 47 D


Sample output:
230

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = 2000001
u = []; r = []; d = []; l = []
for i in range(n):
    A = list(input().split())
    a = [int(A[0]), int(A[1])]
    if A[2] == "U":
        u.append(a)
    elif A[2] == "R":
        r.append(a)
    elif A[2] == "D":
        d.append(a)
    else:
        l.append(a)
#ud
u1 = {}; d1 = {}
for i in range(len(u)):
    if u[i][0] not in u1:
        u1[u[i][0]] = []
    u1[u[i][0]].append(u[i][1])
for i in range(len(d)):
    if d[i][0] not in d1:
        d1[d[i][0]] = []
    d1[d[i][0]].append(d[i][1])
for i in range(200001):
    if i in u1 and i in d1:
        for j in range(len(u1[i])):
            for k in range(len(d1[i])):
                if u1[i][j] < d1[i][k]:
                    b = min(b, (d1[i][k]-u1[i][j])*5)
#rl
r1 = {}; l1 = {}
for i in range(len(r)):
    if r[i][1] not in r1:
        r1[r[i][1]] = []
    r1[r[i][1]].append(r[i][0])
for i in range(len(l)):
    if l[i][1] not in l1:
        l1[l[i][1]] = []
    l1[l[i][1]].append(l[i][0])
for i in range(200001):
    if i in r1 and i in l1:
        for j in range(len(r1[i])):
            for k in range(len(l1[i])):
                if r1[i][j] < l1[i][k]:
                    b = min(b, (l1[i][k]-r1[i][j])*5)
#ur
u2 = {}; r2 = {}
for i in range(len(u)):
    if u[i][0]+u[i][1] not in u2:
        u2[u[i][0]+u[i][1]] = []
    u2[u[i][0]+u[i][1]].append(u[i][0])
for i in range(len(r)):
    if r[i][0]+r[i][1] not in r2:
        r2[r[i][0]+r[i][1]] = []
    r2[r[i][0]+r[i][1]].append(r[i][0])
for i in range(400001):
    if i in u2 and i in r2:
        for j in range(len(u2[i])):
            for k in range(len(r2[i])):
                if r2[i][k] < u2[i][j]:
                    b = min(b, (u2[i][j]-r2[i][k])*10)
#ld
l2 = {}; d2 = {}
for i in range(len(l)):
    if l[i][0]+l[i][1] not in l2:
        l2[l[i][0]+l[i][1]] = []
    l2[l[i][0]+l[i][1]].append(l[i][0])
for i in range(len(d)):
    if d[i][0]+d[i][1] not in d2:
        d2[d[i][0]+d[i][1]] = []
    d2[d[i][0]+d[i][1]].append(d[i][0])
for i in range(400001):
    if i in l2 and i in d2:
        for j in range(len(l2[i])):
            for k in range(len(d2[i])):
                if d2[i][k] < l2[i][j]:
                    b = min(b, (l2[i][j]-d2[i][k])*10)
#lu
l3 = {}; u3 = {}
for i in range(len(l)):
    if l[i][0]-l[i][1] not in l3:
        l3[l[i][0]-l[i][1]] = []
    l3[l[i][0]-l[i][1]].append(l[i][0])
for i in range(len(u)):
    if u[i][0]-u[i][1] not in u3:
        u3[u[i][0]-u[i][1]] = []
    u3[u[i][0]-u[i][1]].append(u[i][0])
for i in range(-200000, 200001):
    if i in l3 and i in u3:
        for j in range(len(l3[i])):
            for k in range(len(u3[i])):
                if u3[i][k] < l3[i][j]:
                    b = min(b, (l3[i][j]-u3[i][k])*10)
#dr
d3 = {}; r3 = {}
for i in range(len(d)):
    if d[i][0]-d[i][1] not in d3:
        d3[d[i][0]-d[i][1]] = []
    d3[d[i][0]-d[i][1]].append(d[i][0])
for i in range(len(r)):
    if r[i][0]-r[i][1] not in r3:
        r3[r[i][0]-r[i][1]] = []
    r3[r[i][0]-r[i][1]].append(r[i][0])
for i in range(-200000, 200001):
    if i in d3 and i in r3:
        for j in range(len(d3[i])):
            for k in range(len(r3[i])):
                if r3[i][k] < d3[i][j]:
                    b = min(b, (d3[i][j]-r3[i][k])*10)
print("SAFE") if b == 2000001 else print(b)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  X = []
  Y = []
  U = []
  time = []
  for i in range(N):
    xappend, yappend, uappend = input().split()
    xappend = int(xappend)
    yappend = int(yappend)
    X.append(xappend)
    Y.append(yappend)
    U.append(uappend)
    if i > 0:
      for j in range(i):
        if U[i] == "U" and U[j] == "D":
          if Y[i] < Y[j] and X[i] == X[j]:
            time.append((Y[j]-Y[i])*5)
  
        elif U[i] == "D" and U[j] == "U":
            if Y[i] > Y[j] and X[i] == X[j]:
              time.append((Y[i]-Y[j])*5)
  
        elif U[i] == "R" and U[j] == "L":
          if X[i] < X[j] and Y[i] == Y[j]:
            time.append((X[j]-X[i])*5)
  
        elif U[i] == "L" and U[j] == "R":
          if X[i] > X[j] and Y[i] == Y[j]:
            time.append((X[i]-X[j])*5)
  
        elif U[i] == "U" and U[j] == "R":
          if X[i] > X[j] and Y[i] < Y[j] and X[i]-X[j] == Y[j]-Y[i]:
            time.append((X[i]-X[j])*10)
  
        elif U[i] == "U" and U[j] == "L":
          if X[i] < X[j] and Y[i] < Y[j] and X[j]-X[i] == Y[j]-Y[i]:
            time.append((X[j]-X[i])*10)
  
        elif U[i] == "D" and U[j] == "R":
          if X[i] > X[j] and Y[i] > Y[j] and X[i]-X[j] == Y[i]-Y[j]:
            time.append((X[i]-X[j])*10)
  
        elif U[i] == "D" and U[j] == "L":
          if X[i] < X[j] and Y[i] > Y[j] and X[j]-X[i] == Y[j]-Y[i]:
            time.append((X[j]-X[i])*10)
  
        elif U[i] == "R" and U[j] == "U":
          if X[i] < X[j] and Y[i] > Y[j] and X[j]-X[i] == Y[i]-Y[j]:
            time.append((X[j]-X[i])*10)
  
        elif U[i] == "R" and U[j] == "D":
          if X[i] < X[j] and Y[i] < Y[j] and X[j]-X[i] == Y[j]-Y[i]:
            time.append((X[j]-X[i])*10)
  
        elif U[i] == "L" and U[j] == "U":
          if X[i] > X[j] and Y[i] > Y[j] and X[i]-X[j] == Y[i]-Y[j]:
            time.append((X[i]-X[j])*10)
  
        elif U[i] == "L" and U[j] == "D":
          if X[i] > X[j] and Y[i] < Y[j] and X[i]-X[j] == Y[j]-Y[i]:
            time.append((X[i]-X[j])*10)
  
  if len(time) > 0:
    time.sort()
    print(time[0])
  else:
    print("SAFE")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

        for px, py in DR[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and py<y:
                ans = min(ans, x-px)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

        for px, py in DR[(x-y)]:
            if px>x: break
            if x>px and py<y:
                ans = min(ans, x-px)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='D':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))
    XYU.append((x, y, u))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    elif u=='L':
        for px, py in UL[(x-y)]:
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if x>px:
                ans = min(ans, (x-px)/2)
                
    elif u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Submission status: Time Limit Exceeded

Solution code:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合
        
    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))
    
    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key
import sys
input = sys.stdin.readline
from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n = int(input())
a = [list(input().split()) for i in range(n)]
for i in range(n):
    if a[i][2] == "R":
        a[i][2] = 1
    elif a[i][2] == "L":
        a[i][2] = 2
    elif a[i][2] == "U" :
        a[i][2] = 3
    else:
        a[i][2] = 4
    a[i][0] = int(a[i][0])
    a[i][1] = int(a[i][1])
a.sort(key=lambda x: x[2])
R1 = defaultdict(Avltree)
R2 = defaultdict(Avltree)
L1 = defaultdict(Avltree)
L2 = defaultdict(Avltree)
U = defaultdict(Avltree)
R = defaultdict(Avltree)

M=10000000
for x, y, u in a:
    if u == 1:
        R1[y - x].insert(x)
        R2[x + y].insert(x)
        R[y].insert(x)
    elif u == 2:
        L1[x + y].insert(x)
        L2[y - x].insert(x)
        k = R[y].search_lower(x, None)
        if k!=None:
            M = min((x - k) * 5, M)

    if u == 3:
        k = L2[y - x].search_higher(x, None)
        if k!=None:
            M = min(M, (k - x) * 10)
        
        k = R2[x + y].search_lower(x, None)
        if k!=None:
            M = min(M, (x - k) * 10)
        
        U[x].insert(y)
    if u == 4:
        k = L1[x + y].search_higher(x, None)
        if k!=None:
            M = min(M, (k - x) * 10)

        k = R1[y - x].search_lower(x, None)
        if k!=None:
            M = min(M, (x - k) * 10)

        k = U[x].search_lower(y, None)
        if k!=None:
            M = min(M, (y - k) * 5)
print(M if M < 10000000 else "SAFE")

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  XYU = [list(map(str,input().split())) for _ in range(N)]
  from collections import deque

  UD = [deque() for _ in range(200001)]
  LR = [deque() for _ in range(200001)]


  for X,Y,u in XYU:
    X = int(X)
    Y = int(Y)
    if u=='R':
      LR[Y].append((X,u))
    elif u=='L':
      LR[Y].append((X,u))
    elif u=='U':
      UD[X].append((Y,u))
    else:
      UD[X].append((Y,u))

  safe = True
  ans = 10**7
  for l in UD:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0])*5)

  for l in LR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='R')and(b[1]=='L'):
          safe = False
          ans = min(ans,(b[0] - a[0])*5)

  del UD
  del LR
  UR = [deque() for _ in range(400001)]
  DL = [deque() for _ in range(400001)]
  DR = [deque() for _ in range(400001)]
  UL = [deque() for _ in range(400001)]


  for X,Y,u in XYU:
    X = int(X)
    Y = int(Y)
    if u=='R':
      UR[X+Y].append((Y,u))
      DR[X-Y+200000].append((Y,u))
    elif u=='L':
      DL[X+Y].append((Y,u))
      UL[X-Y+200000].append((Y,u))
    elif u=='U':
      UR[X+Y].append((Y,u))
      UL[X-Y+200000].append((Y,u))
    else:
      DL[X+Y].append((Y,u))
      DR[X-Y+200000].append((Y,u))
  for l in UR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='R'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in DL:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='L')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in UL:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='L'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in DR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='R')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  if safe:
    print('SAFE')
  else:
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  XYU = [list(map(str,input().split())) for _ in range(N)]
  from collections import deque
  INF = float('inf')

  UD = [deque() for _ in range(200001)]
  LR = [deque() for _ in range(200001)]
  UR = [deque() for _ in range(400001)]
  DL = [deque() for _ in range(400001)]
  DR = [deque() for _ in range(400001)]
  UL = [deque() for _ in range(400001)]


  for X,Y,u in XYU:
    X = int(X)
    Y = int(Y)
    if u=='R':
      LR[Y].append((X,u))
      UR[X+Y].append((Y,u))
      DR[X-Y+200000].append((Y,u))
    elif u=='L':
      LR[Y].append((X,u))
      DL[X+Y].append((Y,u))
      UL[X-Y+200000].append((Y,u))
    elif u=='U':
      UD[X].append((Y,u))
      UR[X+Y].append((Y,u))
      UL[X-Y+200000].append((Y,u))
    else:
      UD[X].append((Y,u))
      DL[X+Y].append((Y,u))
      DR[X-Y+200000].append((Y,u))

  safe = True
  ans = INF
  for l in UD:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0])*5)

  for l in LR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='R')and(b[1]=='L'):
          safe = False
          ans = min(ans,(b[0] - a[0])*5)


  for l in UR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='R'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in DL:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='L')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in UL:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='U')and(b[1]=='L'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  for l in DR:
    length = len(l)
    if length>=2:
      l = sorted(l)
      for i in range(length - 1):
        a = l[i]
        b = l[i+1]
        if (a[1]=='R')and(b[1]=='D'):
          safe = False
          ans = min(ans,(b[0] - a[0]) * 10)

  if safe:
    print('SAFE')
  else:
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XYU = [list(map(str,input().split())) for _ in range(N)]
from collections import deque
INF = float('inf')

UD = [deque() for _ in range(200001)]
LR = [deque() for _ in range(200001)]
UR = [deque() for _ in range(400001)]
DL = [deque() for _ in range(400001)]
DR = [deque() for _ in range(400001)]
UL = [deque() for _ in range(400001)]


for X,Y,u in XYU:
  X = int(X)
  Y = int(Y)
  if u=='R':
    LR[Y].append((X,u))
    UR[X+Y].append((Y,u))
    DR[X-Y+200000].append((Y,u))
  elif u=='L':
    LR[Y].append((X,u))
    DL[X+Y].append((Y,u))
    UL[X-Y+200000].append((Y,u))
  elif u=='U':
    UD[X].append((Y,u))
    UR[X+Y].append((Y,u))
    UL[X-Y+200000].append((Y,u))
  else:
    UD[X].append((Y,u))
    DL[X+Y].append((Y,u))
    DR[X-Y+200000].append((Y,u))
    
safe = True
ans = INF
for l in UD:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='U')and(b[1]=='D'):
        safe = False
        ans = min(ans,(b[0] - a[0])*5)
        
for l in LR:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='R')and(b[1]=='L'):
        safe = False
        ans = min(ans,(b[0] - a[0])*5)
        
        
for l in UR:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='U')and(b[1]=='R'):
        safe = False
        ans = min(ans,(b[0] - a[0]) * 10)
        
for l in DL:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='L')and(b[1]=='D'):
        safe = False
        ans = min(ans,(b[0] - a[0]) * 10)
    
for l in UL:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='U')and(b[1]=='L'):
        safe = False
        ans = min(ans,(b[0] - a[0]) * 10)
        
for l in DR:
  length = len(l)
  if length>=2:
    l = sorted(l)
    for i in range(length - 1):
      a = l[i]
      b = l[i+1]
      if (a[1]=='R')and(b[1]=='D'):
        safe = False
        ans = min(ans,(b[0] - a[0]) * 10)
          
if safe:
  print('SAFE')
else:
  print(ans)