with open('INPUT.TXT') as f:
N, K = f.readline().split()
A = f.read().split()
N, K = int(N), int(K)
P = [[int(A[2 * i]), int(A[2 * i + 1])] for i in range(int((len(A) - 1) / 2))]
G = {x: [] for x in range(1, N + 1)}
for el in P:
G[el[0]].append(el[1])
if len(P) < N - 1:
ans = 'No'
else:
s = 0
for el in P:
if el[1] == K:
s = 1
break
if s == 1:
ans = 'No'
else:
ans = 'Yes'
print(ans)
Комментарий к коду: G = граф в котором если A → B, то лошадь A быстрее B, тогда понятно что если в G меньше чем N - 1 вершин, то информации недостаточно.
Также понятно что граф ацикличен, в противном случае одна лошадь одновременно быстрее и медленее другой, соответственно в нем не более N - 1 ребра.
Остается случай когда ровно N - 1 ребро, несложно понять что он связный, потому достаточно удостоверится в том что indeg(K) \equiv0
Можете на этот код посмотреть, он очевидно рабочий, но memory limit не влезает, что именно съедает так много памяти?
def gege(n, G):
if len(G[n]) == 0:
return []
s = [el for el in G[n]]
for el in G[n]:
s += gege(el, G)
return s
with open('INPUT.TXT') as f:
N, K = f.readline().split()
A = f.read().split()
N, K = int(N), int(K)
P = [[int(A[2 * i]), int(A[2 * i + 1])] for i in range(int((len(A) - 1) / 2))]
G = {x: [] for x in range(1, N + 1)}
for el in P:
G[el[0]].append(el[1])
if len(set(gege(K, G))) == N - 1:
ans = 'Yes'
else:
ans = 'No'
print(ans)
