Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

N, X, Y = map(int, input().split())

# from time import time
# start = time()

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
# appeared_st[0] = 0
n_k = [0] * N
s_t_dict = {}


# def rec(n, dist, s, k, appeared):
#     # print(appeared_st)
#     if dist == k:
#         # if k == 2:
#         #     input()
#         if s < n and n not in appeared_st[s]:
#             appeared_st[s].add(n)
#             appeared_st[0] += 1
#             # print(appeared_st)

#     toes = [node for node in neighbor[n] if node not in appeared]
#     for to in toes:
#         appeared_copy = deepcopy(appeared)
#         appeared_copy.add(to)
#         rec(to, dist+1, s, k, appeared_copy)


def rec(n, dist, s, limit, appeared):
    if s < n:
        ke = "{}.{}".format(s, n)
        if ke in s_t_dict:
            if dist < s_t_dict[ke]:
                n_k[s_t_dict[ke]] -= 1
                s_t_dict[ke] = dist
                n_k[dist] += 1
        else:
            s_t_dict[ke] = dist
            n_k[dist] += 1
            
    # if s < n and n not in appeared_st[s]:
    #     appeared_st[s].add(n)
    #     n_k[dist] += 1
    #     print(appeared_st)
    #     print(n_k)
    #     input()

    if dist == limit:
        return None

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, limit, appeared_copy)


for s in range(1, N):
    rec(s, 0, s, N-1, {s})

for k in range(1, N):
    print(n_k[k])

# for k in range(1, N):
#     tmp = appeared_st[0]

#     for s in range(1, N+1):
#         rec(s, 0, s, k, {s})

    # print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))
            
# print(time() - start)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    cnter = [0] * N

    for start in range(N-1):
        deq = deque()
        deq.append(start)
        n_step = [float('inf')] * N
        n_step[start] = 0
        visited = [False] * N

        while len(deq) > 0:
            fr = deq.popleft()
            visited[fr] = True

            if fr == X-1:
                if not visited[Y-1] or n_step[Y-1] > n_step[X-1]+1:
                    n_step[Y-1] = n_step[X-1]+1
                    deq.append(Y-1)
                    visited[Y-1] = True

            if fr == Y-1:
                if not visited[X-1] or n_step[X-1] > n_step[Y-1]+1:
                    n_step[X-1] = n_step[Y-1]+1
                    deq.append(X-1)
                    visited[X-1] = True
                    
            if fr != N-1:
                if not visited[fr+1] or n_step[fr+1] > n_step[fr]+1:
                    deq.append(fr+1)
                    n_step[fr+1] = n_step[fr]+1
                    visited[fr+1] = True

            if fr != 0:
                if not visited[fr-1] or n_step[fr-1] > n_step[fr]+1:
                    deq.append(fr-1)
                    n_step[fr-1] = n_step[fr]+1
                    visited[fr-1] = True
        
        for i in range(start,N):
            cnter[n_step[i]] += 1
            
    for i in range(1,N):
        print(cnter[i])

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)

for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1

        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1

        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1

        elif(i >= y - 1):
            ans[j - i - 1] += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

def func(mat, d, n):
    def plus(mat, i, j, d, count):
        if mat[i][j] == 0:
            mat[i][j] = d + 1
            count += 1
        return mat, count

    count = 0
    for i in range(1, n+1-d):
        for j in range(i-1+d, n+1):
            if mat[i][j] == d:
                mat, count = plus(mat, i, j-1, d, count)
                mat, count = plus(mat, i, j+1, d, count)
                mat, count = plus(mat, i-1, j, d, count)
                mat, count = plus(mat, i+1, j, d, count)

    return(count)


def main():
    n, x, y = map(int, input().split())
    mat = [[0 for i in range(n+1)] for j in range(n + 1)]
    for i in range(n+1):
        mat[0][i] = -1
        mat[i][n] = -1
    for i in range(1, n+1):
        mat[i][i-1] = -1
    for i in range(1, n):
        mat[i][i] = 1
    mat[x][y-1] = 1

    print(n)
    for d in range(1, n-1):
        print(func(mat, d, n))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
from collections import defaultdict, Counter
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 2 ** 63 - 1

N, X, Y = map(int, input().split(' '))
ad_table = []

for i in range(N):
    tmp = [INF for _ in range(N)]
    tmp[i] = 0
    if i != 0:
        tmp[i-1] = 1
    if i != N - 1:
        tmp[i+1] = 1
    ad_table.append(tmp)
ad_table[X-1][Y-1] = 1
ad_table[Y-1][X-1] = 1

cost_table = floyd_warshall(ad_table)

ans = defaultdict(lambda: 0)
for i in range(N):
    if i+1 == N:
        break
    for k, v in Counter(cost_table[i][i:]).most_common():
        ans[k] += v

for i in range(1, N):
    print(ans[np.float64(i)])

Submission status: Time Limit Exceeded

Solution code:
inputNumbers=input()
N=int(inputNumbers.split(" ")[0])
X=int(inputNumbers.split(" ")[1])
Y=int(inputNumbers.split(" ")[2])

result = []
for k in range(1,N):
    result.append(0)

allBranchLength=[]

for i in range(1, N+1):
    for j in range(i+1,N+1):

        if i <= X:
            if j <= X:
                length = j - i
                allBranchLength.append([str(i) + "," + str(j), length])

            if j > X and j < Y:
                length = X - i + min(j-X, Y-j+1)
                allBranchLength.append([str(i) + "," + str(j), length])

            if j >= Y:
                length = (X - i) + 1 + (j - Y)
                allBranchLength.append([str(i) + "," + str(j), length])

        if i > X and i < Y:
            if j > X and j < Y:
                length = min( (i - X) + 1 + (Y - j) , j - i )
                allBranchLength.append([str(i) + "," + str(j), length])

            if j >= Y:
                length = min( (i - X) + 1 + (j - Y) , j - i )
                allBranchLength.append([str(i) + "," + str(j), length])
                
        if i >= Y:
            if j >= Y:
                length = j - i
                allBranchLength.append([str(i) + "," + str(j), length])


for i in range(len(allBranchLength)):
    result[allBranchLength[i][1] - 1] += 1

for i in range(len(result)):
    print(result[i])

Submission status: Time Limit Exceeded

Solution code:
import queue
n, x, y = map(int, input().split())

lst = [0 for i in range(n)]

for i in range(n-1):
    xx = x-1
    yy = y-1
    q = queue.Queue()
    po = [0 for i in range(n)]
    q.put((i, 0))
    while 1:
        num, leng = q.get()
        if po[num] == 0:
            po[num] = leng
            if i < num and leng < len(lst):
                lst[leng] += 1
            if num < n-1 and po[num+1] == 0:
                q.put((num+1, leng+1))
            if num > 0 and po[num-1] == 0:
                q.put((num-1, leng+1))
            if xx == num:
                q.put((yy, leng+1))
        if q.empty():
            break
for i in range(len(lst)-1):
    print(lst[i+1])

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())



def warshall_floyd(n , x, y):
    d = [0] * n

    for i in range(n):
        d[i] = [0] * n
        for j in range(n):
            if abs(i - j) == 1 or (i == x and j == y ) or (j == x and i == y):
                d[i][j] = 1
            else:
                d[i][j] = 100000
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                next_distance = d[i][k]+d[k][j]
                if next_distance < d[i][j]:
                    d[i][j] = next_distance
    
    distance_map = {i: 0 for i in range(1, n)}
    for i in range(n):
        for j in range(i + 1,n):
            if d[i][j] != 100000:
                distance_map[d[i][j]] += 1  

    for i in range(1, n):
        print(distance_map[i])

warshall_floyd(n, x-1, y-1)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())


arr = [[10**4] * n for i in range(n)]
for i in range(n-1):
        arr[i][i+1] = 1
        arr[i+1][i] = 1
arr[x-1][y-1] = 1
arr[y-1][x-1] = 1

def dk(s,n,w,cost):
    d = [10**4] * n
    us = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not us[i]) and v == -1:
               v = i
            elif (not us[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        us[v] = True
               
        for x in range(n):
               d[x] = min(d[x],d[v]+cost[v][x])
    return d

ans = [0] * (n-1)
for i in range(n):
    dist = dk(i,n,n,arr)
    for j in range(len(dist)):
        ans[dist[j]] += 1

for i in range(1,len(ans)):
    print(ans[i] // 2)
print(0)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = list(map(int, input().split()))
d = [set() for _ in range(n)]
dt = set()

for i in range(1, n):
    t = (i, i+1)
    d[1].add(t)
    dt.add(t)
d[1].add((x,y))
dt.add((x,y))

for k in range(2, n):
    for a in d[1]:
        for b in d[k-1]:
            if a == b: break
            if a[0] == b[0]:
                t = (a[1], b[1]) if a[1] < b[1] else (b[1], a[1])
            elif a[0] == b[1]:
                t = (a[1], b[0]) if a[1] < b[0] else (b[0], a[1])
            elif a[1] == b[0]:
                t = (a[0], b[1]) if a[0] < b[1] else (b[1], a[0])
            elif a[1] == b[1]:
                t = (a[0], b[0]) if a[0] < b[0] else (b[0], a[0])
            if t not in dt:
                d[k].add(t)
                dt.add(t)
for di in d[1:]:
    print(len(di))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d
      
n, x, y = [int(i) for i in input().split()]

dij = Dijkstra(n)

for i in range(n-1):
  dij.add(i, i+1, 1)
dij.add(x-1, y-1, 1)

d = []
for i in range(n):
  d += dij.shortest_path(i)

c = Counter(d)
for i in range(1, n):
  print(c[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N,X,Y = map(int,input().split())
    dp = [[float("inf") for i in range(N)] for j in range(N)]
    heap = []
    heapq.heapify(heap)
    for i in range(N-1):
        dp[i][i+1] = 1
        dp[i+1][i] = 1
        heapq.heappush(heap,(1,i,i+1))
    dp[X-1][Y-1] = 1
    dp[Y-1][X-1] = 1
    heapq.heappush(heap,(1,X-1,Y-1))
    while True:
        if len(heap) == 0 :
            break
        else:
            cost,a,b = heapq.heappop(heap)
            #xを動かす
            for i in [-1,1]:
                if (a + i) < 0 or (a + i) >= N or (a + i) == b :
                    continue
                if dp[a+i][b] > (cost+dp[a][a+i]):
                    dp[a+i][b] = (cost+dp[a][a+i])
                    dp[b][a+i] = (cost+dp[a][a+i])
                    heapq.heappush(heap,(dp[a+i][b],a+i,b))
                if (b + i) < 0 or (b + i) >= N or (b + i) == a :
                    continue
                if dp[a][b+i] > (cost + dp[b][b + i]):
                    dp[a ][b + i] = (cost + dp[b][b + i])
                    dp[b + i][a] = (cost + dp[b][b + i])
                    heapq.heappush(heap, (dp[b + i][a], a, b+ i))

    ans = [0 for i in range(N - 1)]
    for i in range(N):
        for j in range(i+1,N,1):
            if dp[i][j] == float("inf"):
                pass
            else:
                ans[dp[i][j] - 1] += 1
    for i in range(N - 1):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = list(map(lambda x: int(x) ,input().split(" ")))
li = []
result = [ N - i - 1 for i in range(N-1)]

for i in range(N-1):
  l = []
  for k in range(i + 1):
    s = i - k
    l.append((X - s, Y + k))
    l.append((X - s, Y - k))
    l.append((X + s, Y - k))
    l.append((X + s, Y + k))
  l = list(set(l))
  for j in l:
    if not(j[0] <= 0 or j[1] > N):
      if j[1] - j[0]  > i + 1:
        result[i] += 1
        result[j[1] - j[0] -1] -= 1
  print(result[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = map(int,input().split())
cnt = [0]*(n)
path = [(i, i+1) for i in range(n-1)]
path.append((x-1, y-1))
res = []
for i in range(n):
    d = [float('inf')]*n
    que = deque([(i, 0)])
    while que:
        idx, c = que.popleft()
        if d[idx]!=float('inf'):
            continue
        else:
            d[idx] = min(d[idx], c)
            for s,g in path:
                if s==idx:
                    que.append((g, c+1))
                if g==idx:
                    que.append((s, c+1))
    res.append(d)

for r in res:
    for i in range(n-1):
        cnt[i] += r.count(i)
for c in cnt[1:]:
    print(c//2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())

ans = [0 for i in range(N+1)]

for i in range(1,N):
    checking = i

    #まずスタート地点から幅優先探索を実装
    queue = [[i,0]]
    # checked = list(range(1,i+1)) #マス、距離
    checked = [i]

    while(True):
        now = queue[0]

        #ショートカット確認
        if now[0] == X:
            if Y not in checked:
                queue.append([Y,now[1]+1])
                checked.append(Y)
                if not(checking > Y):
                    ans[now[1]+1] += 1
                    # print(now[0],Y,now[1]+1)

        if now[0] == Y:
            if X not in checked:
                queue.append([X,now[1]+1])
                checked.append(X)
                if not(checking > X):
                    ans[now[1]+1] += 1
                    # print(now[0],X,now[1]+1)

        #左
        if now[0]-1 >= 1 and now[0]-1 not in checked:
            queue.append([now[0]-1,now[1]+1])
            checked.append(now[0]-1)
            if not(checking > now[0]-1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]-1,now[1]+1)

        #右
        if now[0]+1 <= N and now[0]+1 not in checked:
            queue.append([now[0]+1,now[1]+1])
            checked.append(now[0]+1)
            if not(checking > now[0]+1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]+1,now[1]+1)

        queue.pop(0)

        if len(checked) == N or len(queue) == 0:
            break

#回答を出力
for i in range(1,N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import OrderedDict
def key(x, y):
    return str(x)+str(y)
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    M = OrderedDict()
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            if M[key(x,y)] > from_cost+1:
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    helper(X, Y, 0)

    cost_list = list(M.values())
    for k in range(N-1):
        print(cost_list.count(k+1))


main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  elif i<x and y-(y-x)//2+1<=j<=y:
    d=y-j+1+x-i
  elif x<=i<=x+(y-x)//2-1 and y<j:
    d=j-y+1+i-x
  elif x<=i and j<=y:
    d=min(j-i,i+y-x+1-j)
  elif i<x and y<j:
    d=j-y+1+x-i
  else:
    d=j-i
  return d
distmap=[dist(k+1,l+1) for k in range(n-1) for l in range(n)]
[print(distmap.count(i+1)) for i in range(n-1)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
from collections import Counter

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n,x,y = map(int,input().split())

# l = [[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]

l = [[0]*n for i in range(n)]
for i in range(n-1):
    l[i][i+1] = 1
    l[i+1][i] = 1 
l[x-1][y-1] = 1
l[y-1][x-1] = 1
# l.append([x,y])

a = np.array(l)
ans = shortest_path(a)
ans_counter = Counter(flatten_2dim(ans))
# values = ans_counter.values()
# print(l)
# print(ans)
for i in range(1,n):
    print(int(ans_counter[i]/2))

Submission status: Time Limit Exceeded

Solution code:
def distanced_nodes(neighbor, start_node, depth_limit):
    visited = [start_node]
    next_nodes = neighbor[start_node]
    depth = 1
    while len(next_nodes) > 0 and depth < depth_limit:
        depth += 1
        queue = next_nodes[:]
        visited += next_nodes
        next_nodes = []
        for q in queue:
            for node in neighbor[q]:
                if node in visited:
                    continue
                else:
                    next_nodes.append(node)
        next_nodes = list(set(next_nodes))
    return next_nodes

N, X, Y = list(map(int, input().split()))
neighbor = { i: [] for i in range(1, N+1) }
for i in range(1,N):
    neighbor[i].append(i+1)
    neighbor[N-i+1].append(N-i)
neighbor[X].append(Y)
neighbor[Y].append(X)

distanced_neighbor = { i: { j: [] for j in range(1, N)} for i in range(1, N+1) }
for i in range(1, N+1):
    visited = [i]
    next_nodes = neighbor[i]
    for j in range(1, N):
        distanced_neighbor[i][j] = next_nodes[:]
        queue = next_nodes[:]
        visited += next_nodes
        next_nodes = []
        for q in queue:
            for node in neighbor[q]:
                if node in visited:
                    continue
                else:
                    next_nodes.append(node)
        next_nodes = list(set(next_nodes))
# for node in distanced_neighbor.keys():
#     print(node, distanced_neighbor[node])

for i in range(1, N):
    res = set()
    for j in range(1, N+1):
        for nei in distanced_neighbor[j][i]:
            if j < nei:
                res.add((j, nei))
            else:
                res.add((nei, j))
    print(len(res))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path
graph = np.zeros((n,n))
for i in range(n-1):
    graph[i][i+1] = 1
    graph[i+1][i] =1
graph[x-1][y-1] = graph[y-1][x-1] = 1
s = shortest_path(graph)
dst = {}
for i in range(n-1):
    for j in range(i+1,n):
        if not s[i][j] in dst.keys():
            dst[s[i][j]] = int(1)
        else:
            dst[s[i][j]] += int(1)
for i in range(1,n):
    if not i in dst.keys():
        print(0)
    else:
        print(dst[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
from collections import defaultdict

N, X, Y = list(map(int, input().split()))

skip_d = abs(X - Y)
d_count = defaultdict(lambda: 0)
# d_table = []
for i in range(N):
    # d_list = []
    for j in range(N):
        if i == j:
            d = 0
            d_count[d] += 1
            # d_list.append(d)
            continue
        # Normal
        min_index = min(i, j)
        max_index = max(i, j)

        if min_index <= X - 1 and Y - 1 <= max_index:
            # 両方外にいる
            d = abs(i - j) - skip_d + 1
        elif X - 1 <= min_index and max_index <= Y - 1:
            # 両方中にいる
            d_1 = abs(i - j)
            x2min = abs(min_index - (X - 1))
            max2y = abs((Y - 1) - max_index)
            d_2 = x2min + max2y + 1
            d = min(d_1, d_2)
        elif max_index <= Y - 1:
            # elif min_index <= X - 1 and X - 1 <= max_index < Y - 1:
            # 大きい方が中にいる
            d_1 = abs(i - j)
            max2y = abs((Y - 1) - max_index)
            min2y = abs(min_index - (Y - 1)) - skip_d + 1
            d_2 = max2y + min2y
            d = min(d_1, d_2)
        elif X - 1 <= min_index:
            # elif X - 1 <= min_index < Y - 1 and Y - 1 <= max_index:
            # 小さい方が中にいる
            d_1 = abs(i - j)
            d_2 = (abs(max_index - (X - 1)) - skip_d + 1) + abs((X - 1) - min_index)
            d = min(d_1, d_2)

        # d_list.append(d)
        d_count[d] += 1
    # d_table.append(d_list)

ans_s = []
for k in range(1, N):  # 2 * 10 ** 3
    c = d_count[k]
    c = c // 2
    ans_s.append(str(c))
ans = "\n".join(ans_s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]
        
n, x, y = map(int,input().split())
ans = collections.defaultdict(int)

edges = [[i, i+1, 1] for i in range(1, n)]
edges += [[x, y, 1]]

graph1 = Dijkstra()

for u, v, a in edges:
    graph1.add(u,v,a)

for i in range(1,n+1):
    result_a = graph1.search(i)
    for j in range(i+1, n+1):
        ans[result_a[j]] += 1

for i in range(1,n-1):
    print(ans[i])
print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path,floyd_warshall,dijkstra,bellman_ford,johnson
from scipy.sparse import csr_matrix
N,X,Y = map(int,input().split())

#隣接リストの整備
"""
route_list = np.zeros((N,N))
route_list[0][1] = 1
for i in range(1,N-1):
    route_list[i][i-1] = 1
    route_list[i][i+1] = 1
print(route_list)
route_list[-1][-2] = 1
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1
"""
a = np.array([1]*(N-1))
route_list = np.diag(a,k=1)
#b = np.diag(a,k=1)
#c = np.diag(a,k=-1)
#route_list = b | c
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1

shortest = shortest_path(route_list,directed=False)

for i in range(1,N):
    print(np.count_nonzero(shortest == i)//2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
n, x, y = map(int, input().split())
ans = [0] * (n - 1)
table = []
for i in range(n):
    l = [0] * n
    if i + 1 < n:
        l[i + 1] = 1
    if i - 1 > -1:
        l[i - 1] = 1
    if i == x - 1:
        l[y - 1] = 1
    if i == y - 1:
        l[x - 1] = 1
    table.append(l)
a = shortest_path(np.array(table))
a = a.flatten().tolist()
for i in range(1, n):
    print(a.count(i) // 2)

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*n
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    q = queue.Queue()
    for i in range(n):
        f = [True]*n
        f[i] = False
        q.put([i, 0])
        while not q.empty():
            a, b = q.get()
            for v in t[a]:
                if 0 < v and v < n:
                    if f[v]:
                        if i < v:
                            ans[b + 1] += 1
                        f[v] = False
                        if i < v or (i <= (x+y+1)//2 and x <= v):
                            q.put([v, b+1])
    for i in range(1, n):
        print(ans[i])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())

X -= 1
Y -= 1

print(N)

def disdance(i, j):
    if i <= X and j >= Y:
        return X - i + j - Y + 1
    elif i >= X and j <= Y:
        return min(j - i, i - X + Y - j + 1)
    elif i >= X and j >= Y:
        return min(j - i, i - X + j - Y + 1)
    elif i <= X and j <= Y:
        return min(j - i, X - i + Y - j + 1)

d = []

for i in range(N - 1):
    for j in range(i + 1, N):
        d.append(disdance(i, j))

for k in range(2, N):
    print(d.count(k))

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        a = j-i
        b = min(abs(x-1-i), abs(y-1-i)) + 1 + min(abs(y-1-j), abs(x-1-j))
        dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)