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:
import itertools
n,x,y = map(int,input().split())
bl = []
al = []
cl = []
dl = []
el = []
for i in range(1,n+1):
    bl.append(i)
i = 1
while(i < n+1):
    al.append(i)
    if i == x:
        i = y
    else:
        i+=1
reverseflag = False
i = 1
for _ in range(y):
    cl.append(i)
    if i == x:
        reverseflag = True
        i = y
    else:
        if reverseflag:
            i-=1
        else:
            i+=1
i = x + (y-x)//2
for _ in range(y-x+1):
    dl.append(i)
    if i == x:
        i = y
    else:
        i-=1
i = x + (y-x)//2
reverseflag = True
while(i != n+1):
    el.append(i)
    if i == x:
        reverseflag = False
        i = y
    else:
        if reverseflag:
            i-=1
        else:
            i+=1
zeroflag = False
m = len(al)
mm = len(cl)
mmm = len(dl)
mmmm = len(el)
dict = {}
for b in itertools.combinations(bl,2):
    dict.update({str(b):False})
for k in range(1,n):
    tmpans = 0
    if zeroflag:
        print(0)
        continue
    tmp = []
    for i in range(n):
        if k+i < n:
            left = min(bl[i],bl[i+k])
            right = max(bl[i],bl[i+k])
            tmpkey = (left,right)
            if dict[str(tmpkey)] == False:
                tmp.append((bl[i],bl[i+k]))
                dict[str(tmpkey)] = True
        if k+i < m:
            left = min(al[i],al[i+k])
            right = max(al[i],al[i+k])
            tmpkey = (left,right)
            if dict[str(tmpkey)] == False:
                tmp.append((al[i],al[i+k]))
                dict[str(tmpkey)] = True
        if k+i < mm:
            left = min(cl[i],cl[i+k])
            right = max(cl[i],cl[i+k])
            tmpkey = (left,right)
            if dict[str(tmpkey)] == False:
                tmp.append((cl[i],cl[i+k]))
                dict[str(tmpkey)] = True
        if k+i < mmm:
            left = min(dl[i],dl[i+k])
            right = max(dl[i],dl[i+k])
            tmpkey = (left,right)
            if dict[str(tmpkey)] == False:
                tmp.append((dl[i],dl[i+k]))
                dict[str(tmpkey)] = True
        if k+i < mmmm:
            left = min(el[i],el[i+k])
            right = max(el[i],el[i+k])
            tmpkey = (left,right)
            if dict[str(tmpkey)] == False:
                tmp.append((el[i],el[i+k]))
                dict[str(tmpkey)] = True
    tmp = set(tmp)
    tmpans=len(tmp)
    print(tmpans)
    if tmpans == 0:
        zeroflag = True

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
# n, x, y = 7, 3, 7
edge = [[] for _ in range(n+1)]
dist = [[abs(i-j) for i in range(n+1)] for j in range(n+1)]
counter = [0 for i in range(n)]
for i in range(1, n):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x].append(y)
edge[y].append(x)
# print(edge)
for i in range(n):
    for j in range(i+1, n+1):
        new_dist = abs(x-i)+abs(y-j)+1
        if new_dist < dist[i][j]:
            dist[i][j] = new_dist
            dist[j][i] = new_dist

for i in range(1, n+1):
    for num in dist[i][1:]:
        counter[num] += 1
# print(dist)

for num in counter[1:]:
    print(num//2)

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
        if a == 1:
            dist = 1
        else:
            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)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict, deque

N, X, Y = [int(x) for x in input().split()]


def bfs(source):
    q = deque([source])
    dist = {source: 0}
    while q:
        i = q.popleft()
        d = dist[i]
        nbr = []
        if i - 1 >= 1:
            nbr.append(i - 1)
        if i + 1 <= N:
            nbr.append(i + 1)
        if i == X:
            nbr.append(Y)
        if i == Y:
            nbr.append(X)
        for j in nbr:
            if j not in dist:
                q.append(j)
                dist[j] = d + 1
    return dist


count = Counter()
for i in range(1, N + 1):
    dist = bfs(i)
    assert len(dist) == N
    for j, d in dist.items():
        if i < j:
            count[d] += 1

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

Submission status: Time Limit Exceeded

Solution code:
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 i in range(1, N):
    print(sum([len(distanced_neighbor[j][i]) for j in range(1, N+1)])//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
l[1].append(2)
for i in range(2,n):
    l[i].append(i+1)
    l[i].append(i-1)
l[n].append(n-1)
l[x].append(y)
l[y].append(x)
clist = [0]*(n+1)
#ここまでで、グラフが隣接リスト表記で表される
for k in range(1,n+1):
    d = deque()
    dist = [-1]*(n+1)
    dist[k] = 0
    d.append(k)
    while True:
        v = d.popleft()
        for i in l[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        if not d:
            break
    for j in dist[k+1:]:
        clist[j] += 1
for i in range(1,n):
    print(clist[i])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost, pre):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    for i in range(len(pre)):
        d[i] = pre[i]
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(len(pre), n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

n, a, b = map(int, input().split())

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    # x,y,z = map(int,input().split())
    # cost[x][y] = z
    # cost[y][x] = z
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[a-1][b-1] = 1
cost[b-1][a-1] = 1


ANS = []
for i in range(n):
    pre = []
    for j in range(i):
        pre.append(ANS[j][i])

    ANS.append(dijkstra(i, n, n, cost, pre))
# print(ANS)
from functools import reduce
A = reduce(lambda x,y: x+y,ANS)

import collections

c = collections.Counter(A)

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
S = [sorted(list(range(1, i+1)), reverse=True) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

"""for _ in range(2):
    for k in range(X-1, Y-1):
    #for k in range(N):
        for i in range(N):
            for j in range(N):
                    S[i][j] = min(S[i][j], S[i][k]+S[k][j])"""

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+S[x][y]+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])

Submission status: Time Limit Exceeded

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

result = []
for i in range(1, N+1):
    for j in range(i, N+1):
        if j<=X:
            result.append(j-i)
        elif (i<=X)&(X<j<=Y):
            if (j-i)<=(Y-j+1+X-i):
                result.append(j-i)
            else:
                result.append(Y+X-j-i+1)
        elif (i<=X)&(Y<=j):
            result.append(j-Y+1+X-i)
        elif (X<i)&(j<=Y):
            if (j-i)<=(Y-j+1+i-X):
                result.append(j-i)
            else:
                result.append(Y-j+1+i-X)
        elif (X<i)&(Y<j):
            if (j-i)<=(j-Y+1+i-X):
                result.append(j-i)
            else:
                result.append(j-Y+1+i-X)
        else:
            #print(i, j)
            pass
            
for i in range(N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

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

m = [[0 for i in range(n)] for j in range(n)]

def check(i, j):
    if -1 < i and i < n and -1 < j and j < n and i < j:
        if m[i][j] == 0:
            return True
    return False

def mark(i, j, c):
    if check(i-1, j):
        m[i-1][j] = c
    if check(i+1, j):
        m[i+1][j] = c
    if check(i, j-1):
        m[i][j-1] = c
    if check(i, j+1):
        m[i][j+1] = c

for i in range(n-1):
    m[i][i+1] = 1

m[x-1][y-1] = 1

for c in range(n):
    for i in range(n):
        for j in range(n):
            if 1 < c and m[i][j] == c-1:
                mark(i, j, c)

import itertools
l = list(itertools.chain.from_iterable(m))

for i in range(n-1):
    print(l.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
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.ones(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:
# coding: utf-8
# Your code here!
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._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

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

    V=N
    djk = Dijkstra(V)

    for i in range(N-1):
        djk.add(i,i+1,1)
        djk.add(i+1,i,1)
    djk.add(X-1,Y-1,1)
    djk.add(Y-1,X-1,1)
    
    
    count=[0]*N
    
    for i in range(N-1):
        # j=0
        for j in range(i,N):
            # print(djk.shortest_path(j))
            count[djk.shortest_path(j)[i]]+=1
    # print(d)
    for i in range(1,N):
        print(count[i])
main()

Submission status: Time Limit Exceeded

Solution code:



def main():
    # import numpy as np
    N, X, Y = map(int, input().split())

    path_len = Y-X
    G = [0]*N
    for i in range(N):
        if i == 0:
            G[0] = [1]
        elif i == N-1:
            G[N-1] = [N-2]
        else:
            G[i] = [i-1, i+1]
        if i+1 == X:
            G[i].append(Y-1)
        if i+1 == Y:
            G[i].append(X-1)
    # print(G)
    D =[0]*N
    for j,g in enumerate(G):
        D[j] = [1 if i in g else N for i in range(N)]
    
    # from pprint import pprint 
    # pprint(D)
    # D =np.array(D)

    for k in range(N):
        for i in range(N):
            if N == D[i][k]:
                continue
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    # pprint(D)
    D=sum(D, [])

    for i in range(1,N):
        tmp = D.count(i)
        if i ==2:
            tmp = tmp - N
        print(tmp//2)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

X = X-1
Y = Y-1

for kIndx in range(1, N):
    kNum = 0

    for jIndx in range(N):
        for iIndx in range(jIndx):
            if (jIndx <= X) or (iIndx >= Y):
                if jIndx - iIndx == kIndx:
                    kNum += 1
            elif (iIndx <= X) and (jIndx >= Y):
                if (jIndx - iIndx) - (Y - X -1) == kIndx:
                    kNum += 1
            elif (iIndx <= X) and ((jIndx > X) and (jIndx < Y)):
                if 2 * jIndx - (X + Y) - 1 > 0:
                    if (jIndx - iIndx) - (2 * jIndx - (X + Y) - 1) == kIndx:
                        kNum += 1
                else:
                    if jIndx - iIndx == kIndx:
                        kNum += 1
            elif ((iIndx > X) and (iIndx < Y)) and (jIndx >= Y):
                if (X + Y) - 2 * iIndx - 1 > 0:
                    if (jIndx - iIndx) - ((X + Y) - 2 * iIndx - 1) == kIndx:
                        kNum += 1
                else:
                    if jIndx - iIndx == kIndx:
                        kNum += 1
            else:
                if (2 * (jIndx - iIndx) - (Y - X) - 1) > 0:
                    if (jIndx - iIndx) - (2 * (jIndx - iIndx) - (Y - X) - 1) == kIndx:
                        kNum += 1
                else:
                    if jIndx - iIndx == kIndx:
                        kNum += 1
    print(kNum)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-02-21 20:39:32 +0900
# LastModified: 2020-03-28 22:32:08 +0900
#

from collections import Counter
import heapq

N, X, Y = map(int, input().split())
count = [0]*N
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
def initial_signal(i,adj,N):
    d = [float("inf") for _ in range(N)]
    d[i] = 0
    Q = [(0,i)]
    return d,Q

def relax(n_cost, u, v, adj,d,Q):
    if d[v] > d[u]+n_cost:
        d[v]=d[u]+n_cost
        heapq.heappush(Q,(d[v],v))



def dijkstra(i,adj,N):
    d,Q = initial_signal(i,adj,N)
    while Q:
        cost, u = heapq.heappop(Q)
        for n_cost, v in adj[u]:
            relax(n_cost, u, v, adj, d, Q)
    for unko in d:
        count[unko]+=1





adj = [[] for _ in range(N)]
for i in range(1,N):
    adj[i].append((1,i-1))
    adj[i-1].append((1,i))
adj[X-1].append((1,Y-1))
adj[Y-1].append((1,X-1))




for i in range(N):
    dijkstra(i,adj,N)


print(N)
for i in range(2,N-1):
    print(count[i]//2)
print(0)

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])
  if result[i] == 0:
    for j in range(N -i - 2) :
      print(0)
    break

Submission status: Time Limit Exceeded

Solution code:
(N,X,Y) = map(int,input().split())
dist = []
dist.append([])
dist_all =[]
for i in range(1,N):
    dist[0].append((i,i+1))
    dist_all.append((i,i+1))
dist[0].append((X,Y))
dist_all.append((X,Y))
print(len(dist[0]))
a = 0
b = 0
for k in range(2,N):
    pre1 = dist[a]
    pre2 = dist[b]
    dist.append([])
    for i in pre1:
        for j in pre2:
            if i[1] == j[0] and i[0] != j[1]:
                Candi = (i[0],j[1])
                if Candi not in dist_all:
                    dist[k-1].append(Candi)
                    dist_all.append(Candi)
            if i[1] == j[1] and i[0] != j[0]:
                Candi = (min(i[0],j[0]),max(i[0],j[0]))
                if Candi not in dist_all:
                    dist[k-1].append(Candi)
                    dist_all.append(Candi)
            if i[0] == j[0] and i[1] != j[1]:
                Candi = (min(i[1],j[1]),max(i[1],j[1]))
                if Candi not in dist_all:
                    dist[k-1].append(Candi)
                    dist_all.append(Candi)
    if k % 2 == 0:
        a += 1
    else:
        b += 1
    print(len(dist[k-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import  dijkstra
from scipy.sparse import csr_matrix

n,x,y = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]

for i in range(n-1):
    graph[i][i+1] = 1
    graph[i+1][i] = 1
    
graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

ans = dijkstra(graph )

for i in range(1,n):
    print(int(np.count_nonzero(ans == i)/2))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def warshall_floyd(dist):
    for k, _ in enumerate(dist):
        for i, _ in enumerate(dist):
            for j, _ in enumerate(dist):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


N, X, Y = map(int, read().split())
c = [[N + 10] * N for _ in range(N)]
for i in range(N - 1):
    c[i][i] = 0
    c[i][i + 1] = 1
    c[i + 1][i] = 1
c[N - 1][N - 1] = 0
c[X - 1][Y - 1] = 1
c[Y - 1][X - 1] = 1

cc = sum(warshall_floyd(c), [])

for i in range(1, N):
    print(cc.count(i) // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())

graph = []
graph.append([1])
for i in range(1, N-1):
    graph.append([i-1, i+1])
graph.append([N-2])

graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

cnt = [0]*N

def bfs(num):
    dq = deque()
    dq.append((num,0))
    visited = [-1]*N
    visited[num] = 0
    while dq:
        a, b = dq.popleft()
        for i in graph[a]:
            if visited[i] == -1:
                visited[i] = b+1
                dq.append((i, b+1))

    for i in visited:
        if i > 0:
            cnt[i] += 1
    return cnt
for i in range(N): bfs(i)
for i in cnt[1:]:
    print(i//2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def get_d_min(a, b, X, Y):

    d = abs(a - b)
    if a == X and b == Y:
        d = 1
    elif a <= X and b > X and b <= Y:
        dd = (X - a) + (Y - b) + 1
        d = min(d, dd)
    elif a >= X and a < Y and b >= Y:
        dd = (a - X) + (b - Y) + 1
        d = min(d, dd)
    elif a > X and b < Y:
        dd = (a - X) + (Y - b) + 1
        d = min(d, dd)
    elif a < X and b > Y:
        dd = (X - a) + (b - Y) + 1
        d = min(d, dd)
    return d

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

comb = combinations(range(1, N + 1), 2)

counts = [0] * N
for a, b in comb:
    a, b = min(a, b), max(a, b)
    d_min = get_d_min(a, b, X, Y)
    counts[d_min] += 1

for count in counts[1:]:
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import shortest_path
import numpy as np

NXY = input().split()
N = int(NXY[0])
X = int(NXY[1])
Y = int(NXY[2])

adj_matrix = np.zeros((N,N))
for i in range(N-1):
    adj_matrix[i,i+1] = 1
    adj_matrix[i+1,i] = 1

adj_matrix[X-1,Y-1] = 1
adj_matrix[Y-1,X-1] = 1
result = np.ravel(shortest_path(adj_matrix))
for i in range(1,N):
    print(int(np.count_nonzero(result == i)/2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

g = np.zeros((n, n), dtype=int)

# print(g)

for i in range(n):
  for j in range(i+1, n):
    if j != y-1:
      g[i,j] = g[i,j-1] + 1
    elif i < x:
      g[i,j] = g[i,x-1] + 1
    else: 
      g[i,j] = min((g[i,j-1] + 1), i+1-x + 1)

# print(g)

for i in range(n):
  for j in range(y-1, x, -1):
    if g[i,j] + 1 < g[i,j-1]:
      g[i,j-1] = g[i,j] + 1

# print(g)

for i in range(1, n):
  print(np.count_nonzero(g == i))

Submission status: Time Limit Exceeded

Solution code:
#python3
from collections import deque
from collections import Counter
from collections import defaultdict
INF = int(1e9)
def main():
    n, x, y = map(int, input().split())
    x-=1
    y-=1
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[i].append(i+1)
        g[i+1].append(i)
    g[x].append(y)
    g[y].append(x)
    ans = defaultdict(int)
    q = deque()
    pns = []
    for i in range(n):
        #i番目から探索を始める
        #distがkになったときカウントする
        #キューが空になったら次のノードをスタートとして探索する
        dist = [INF for _ in range(n)]
        q.append(i)
        dist[i] = 0
        while len(q):
            node_s = q.popleft() 
            for j in range(len(g[node_s])):
                if dist[g[node_s][j]] != INF:
                    continue
                q.append(g[node_s][j])
                dist[g[node_s][j]] = dist[node_s] + 1
        for k in range(n): 
            pns.append(dist[k])
    
    ans = Counter(pns) 
    for k in range(1, n):
        print(ans[k]//2)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

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

l1 = np.linspace(1,1,N-1)
l = np.diag(l1,k=1) + np.diag(l1,k=-1)

l[X-1,Y-1] = 1
l[Y-1,X-1] = 1

spath = shortest_path(l,directed=False,unweighted=True)

for i in range(N-1):
    ans = int(np.count_nonzero(spath==i+1)/2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    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)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#abc160 d
from collections import deque
import itertools
n,x,y=map(int,input().split())
g=[[False]*n for _ in range(n)]

for i in range(n-1):
    g[i][i+1]=True
    g[i+1][i]=True
g[x-1][y-1]=True
g[y-1][x-1]=True

def bfs(s,e):
    color=[False]*n
    dis=[0]*n
    q=deque()
    q.append(s-1)
    color[s-1]=True

    while q:
        now=q.popleft()

        if now==(e-1):
            break
        for i in range(n):
            if g[now][i]==True and color[i]==False:
                dis[i]+=dis[now]+1
                color[i]=True
                q.append(i)
    return dis[e-1]
l=[i for i in range(1,n+1)]
c=itertools.combinations(l,2)
ans=[0]*n
for s,e in c:
    distance=bfs(s,e)
    ans[distance]+=1
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra

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

route = [[0 for _ in range(n)]for _ in range(n)]
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)


ans = [0 for _ in range(n)]
for i in range(n):
	for j in range(i,n):
		ans[int(res[i][j])] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

d = [[2000 for _ in range(N)] for _ in range(N)]

for i in range(N):
  d[i][i] = 0
  if i == N-1:
    pass
  else:
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

INF = int(1e9+7)

def dijkstra(s,n,w,cost):
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
               
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

def main():
    n, x, y = na()

    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in range(n-1):
        cost[i][i+1] = 1
        cost[i+1][i] = 1
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1

    kyo = 1
    ans = dict()
    for i in range(n):
        for s in dijkstra(i, n, n-1, cost)[i+1:]:
            if s in ans:
                ans[s] += 1
            else:
                ans[s] = 1
    
    for i in range(n-1):
        if i+1 in ans:
            print(ans[i+1])
        else:
            print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
from collections import Counter

N, X, Y = map(int, sys.stdin.readline().rstrip().split())

nodes = list(range(1, N + 1))
distance_counter = Counter()
a = Y - X - 1
p = (Y - X) // 2 + X
for i, j in combinations(nodes, 2):
    if j - i == 1:
        distance = 1
        distance_counter[distance] += 1
        continue
    if i <= X:
        if j < Y:
            jtoX = min(Y - j + 1, j - X)
            distance = X - i + jtoX
        else:
            distance = j - i - a
    else:
        if j < Y:
            d1 = j - i
            d2 = i - X + Y - j + 1
            distance = min(d1, d2)
        else:
            itoY = min(i - X + 1, Y - i)
            distance = j - Y + itoY
    distance_counter[distance] += 1

for k in range(1, N):
    if k == 1:
        print(N)
    else:
        print(distance_counter.get(k, 0))