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:
n, x, y = map(int, input().split())
x, y = x-1, y-1


def update(dist, queue, d, x):
    if dist[x] >= 0: return dist, queue
    dist[x] = d+1
    queue.append(x)
    return dist, queue

ans = [0 for _ in range(n)]
for i in range(n):
    dist = [-1 for _ in range(n)]
    dist[i] = 0
    queue = [i]
    while True:
        if len(queue) == 0: break
        now = queue.pop(0)
        d = dist[now]
        if now-1 >= 0:
            dist, queue = update(dist, queue, d, now-1)
        if now+1 < n:
            dist, queue = update(dist, queue, d, now+1)
        if now == x:
            dist, queue = update(dist, queue, d, y)
        if now == y:
            dist, queue = update(dist, queue, d, x)
    for d in dist:
        ans[d] += 1

for a in ans[1:]:
    print(a//2)

Submission status: Time Limit Exceeded

Solution code:
import collections
n, x, y = map(int, input().split())
lst = []
for i in range(1, n+1):
  for j in range(i, n+1):
    tmp = min(abs(i-j), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(x-j))
    lst.append(tmp)
lst = collections.Counter(lst)
for i in range(1, n):
  print(lst[i])

Submission status: Time Limit Exceeded

Solution code:
in_list = [int(n) for n in input().split()]

N = in_list[0]
X = in_list[1]
Y = in_list[2]

def build_graph(N,X,Y):
    graph = {}
    for n in range(1,N+1):
        graph[n] = set()
        if n < N:
            graph[n] = graph[n] | {n+1}
        if n > 1:
            graph[n] = graph[n] | {n-1}
        if n == X:
            graph[n] = graph[n] | {Y}
        if n == Y:
            graph[n] = graph[n] | {X}
    return graph

graph = build_graph(N,X,Y)

def n_neighbour(node,step):
    neighbours = set()
    if step == 1:
        neighbours = graph[node]
    else:
        for next in graph[node]:
            neighbours = neighbours | n_neighbour(next,step-1)
    return neighbours - {node}

def build_dist(node):
    dist = {}
    for step in range(1,N): #N+1?
        dist[step] = set()
        for neighbour in n_neighbour(node,step):
            membership = 0
            for val in dist.values():
                if neighbour in val:
                    membership = 1
                    break
            if membership == 0:
                dist[step] = dist[step] | {neighbour}
    return dist

def filter_dist(node):
    dist = build_dist(node)
    for key in range(N):
        if key in dist:
            dist[key] = {n for n in dist[key] if n > node}
            if not dist[key]:
                del dist[key]
    return dist

def get_total(step):
    total = 0
    for node in graph:
        dict = filter_dist(node)
        if step in dict:
            total += len(filter_dist(node)[step])
    return total

for step in range(1,N):
    print(get_total(step))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

a = [i for i in range(1, n+1)]
b = list(itertools.combinations(a, 2))
c = [0]*(n-1)

for j in range(len(b)):
    d = min(abs(b[j][0]-b[j][1]), abs(x-b[j][0])+1+abs(b[j][1]-y), abs(y-b[j][0])+1+abs(b[j][1]-x))
    c[d-1] += 1

for k in range(n-1):
    print(c[k])

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

a = [i for i in range(1, n+1)]
b = list(itertools.combinations(a, 2))
c = [0]*len(b)

for j in range(len(b)):
    c[j] = min(abs(b[j][0]-b[j][1]), abs(x-b[j][0])+1+abs(b[j][1]-y), abs(y-b[j][0])+1+abs(b[j][1]-x))

for k in range(1, n):
    print(c.count(k))

Submission status: Time Limit Exceeded

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

count=[0]*N

def bfs(start):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=queue.Queue()
    q.put([start,0])
    dist[start]=0
    while not q.empty():
        j,kyori=q.get()

        if j-1>=1:
            if dist[j-1]==-1:
                q.put([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.put([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.put([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.put([X,kyori+1])
            dist[X]=kyori+1

    return dist[1:]

def main():
    for start in range(1,N+1):
        #dist=bfs(start)
        for d in bfs(start):
            count[d]+=1

    for i in count[1:]:
        print(i//2)

main()

Submission status: Time Limit Exceeded

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

count=[0]*N

def bfs(start):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=queue.Queue()
    q.put([start,0])
    dist[start]=0
    while not q.empty():
        j,kyori=q.get()

        if j-1>=1:
            if dist[j-1]==-1:
                q.put([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.put([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.put([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.put([X,kyori+1])
            dist[X]=kyori+1

    return dist[1:]

def main():
    for start in range(1,N+1):
        dist=bfs(start)
        for d in dist:
            count[d]+=1

    for i in count[1:]:
        print(i//2)

main()

Submission status: Time Limit Exceeded

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

graph = {i: [] for i in range(1, n + 1)}
graph[x].append(y)
graph[y].append(x)
for i in range(1, n):
    graph[i].append(i + 1)
    graph[i + 1].append(i)

tf = [[False] * (n + 1) for i in range(n + 1)]
ans = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v, 0, v])
    voi[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        depth = sub[1]
        before = sub[2]
        if tf[now][v] == False:
            ans[depth] += 1
            tf[now][v] = True
            tf[v][now] = True
        for next in graph[now]:
            if voi[next]:
                continue
            voi[next] = True
            q.put([next, depth + 1, now])

for i in range(1, n + 1):
    voi = [False] * (n + 1)
    bfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = [0] * n

# deque の代わりにタプルを使い捨てにしてみる。
# quが未定義だと言われる，なんで，グローバルじゃないの？
# じゃない。nonlocal宣言で解決した。


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = (start_v,)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        nonlocal qu
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu = qu + (v,)

    push(start_v, 0)

    while len(qu):
        v = qu[0]
        qu = qu[1:]
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

    for i in range(n):
        ans[dist[i]] += 1


def main():
    for i in range(n):
        bfs(i)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import queue

'''
TLE code

'''

def push_property(h, cost, v, d) :
    if cost[v] != float('INF') :
        return
    heapq.heappush(h, [d, v])
    cost[v] = d


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

ans = [0] * n

for i in range(n) :
    h = []
    heapq.heapify(h)
    heapq.heappush(h, [0, i])
    cost = [float('INF') for _ in range(n)]
    push_property(h, cost,  i, 0)
    while len(h) != 0 :
        v = heapq.heappop(h)[1]
        d = cost[v]

        #print(i, v, d, cost, 'IN')
        #print(v, d)
        if v+1 < n :
            push_property(h, cost, v+1, d+1)
        if v-1 >= 0 :
            push_property(h, cost, v-1, d+1)
        if v == x :
            push_property(h, cost, y, d+1)
        if v == y:
            push_property(h, cost, x, d+1)
        #print(i, v, d, cost)
    for j in range(n) :
        ans[cost[j]] += 1

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

Submission status: Time Limit Exceeded

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

G = [[] for _ in range(N)]
# print(G)
# ぐらふの作成
for i in range(N-1):
    G[i].append(i+1)
    G[i+1].append(i)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

# print(G)

from collections import deque
def bfs(G,v):
    que = deque([v])
    dist[v] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)

D = [0]*(N-1)
for i in range(N):
    dist = [-1]*N
    bfs(G,i)
    # print(dist)
    for d in dist:
        if d>0:
            D[d-1] += 1
# print(D)
for d in D:
    print(d//2)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
	N, X, Y = map(int, input().split())

	ans = [0] * (N - 1)

	for i in range(1,N):
		for j in range(i+1,N+1):
			l1 = abs(j-i)
			l2 = abs(X-i) + 1 + abs(j-Y)
			l3 = abs(Y-i) + 1 + abs(j-X)
			lm = min(l1,l2,l3)
			ans[lm - 1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
	N, X, Y = map(int, input().split())

	ans = 0

	for k in range(1,N):
		ans = 0
		for i in range(1,N):
			for j in range(i+1,N+1):
				l1 = abs(j-i)
				l2 = abs(X-i) + 1 + abs(j-Y)
				l3 = abs(Y-i) + 1 + abs(j-X)

				lm = min(l1,l2,l3)

				if lm == k:
					ans += 1

		print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
def main():
    input = sys.stdin.readline

    def dijkstra(s,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * n
        used = [True] * n #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for a,b in edge[s]:
            heapq.heappush(edgelist,a*(10**6)+b)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge%(10**6)]:
                continue
            v = minedge%(10**6)
            d[v] = minedge//(10**6)
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
        return d

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

    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(n-1):
        edge[i].append((1,i+1))
        edge[i+1].append((1,i))
    edge[x-1].append((1,y-1))
    edge[y-1].append((1,x-1))

    for i in range(n):
        edge[i] = tuple(edge[i])
    edge = tuple(edge)

    ans = [0 for _ in range(n)]
    for i in range(n):
        #dijkstra(始点,edge)
        res = dijkstra(i,edge)
        for j in range(i+1,n):
            ans[res[j]] += 1

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    edge[i].append((1,i+1))
    edge[i+1].append((1,i))
edge[x-1].append((1,y-1))
edge[y-1].append((1,x-1))

for i in range(n):
    edge[i] = tuple(edge[i])
edge = tuple(edge)

ans = [0 for _ in range(n)]
for i in range(n):
    #dijkstra(始点,edge)
    res = dijkstra(i,edge)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    edge[i].append((1,i+1))
    edge[i+1].append((1,i))
edge[x-1].append((1,y-1))
edge[y-1].append((1,x-1))

for i in range(n):
    edge[i] = tuple(edge[i])
edge = tuple(edge)

ans = [0 for _ in range(n)]
for i in range(n):
    #dijkstra(始点,edge)
    res = dijkstra(i,edge)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("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

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

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
cost = [[float("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

for i in range(n):
    cost[i] = tuple(cost[i])
cost = tuple(cost)

ans = [0 for _ in range(n)]
for i in range(n):
    #nは頂点数、wは辺の数
    res = dijkstra(i,n,n,cost)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("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

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

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
cost = [[float("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

cost = tuple(cost)

ans = [0 for _ in range(n)]
for i in range(n):
    #nは頂点数、wは辺の数
    res = dijkstra(i,n,n,cost)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("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 tuple(d)

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

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
cost = [[float("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

ans = [0 for _ in range(n)]
for i in range(n):
    #nは頂点数、wは辺の数
    res = dijkstra(i,n,n,cost)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("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

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

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
cost = [[float("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

ans = [0 for _ in range(n)]
for i in range(n):
    #nは頂点数、wは辺の数
    res = dijkstra(i,n,n,cost)
    for j in range(i+1,n):
        ans[res[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = np.zeros(N-1, int)

for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        ans[min(d1, d2) - 1] += 1

[print(ans[i]) for i in range(N - 1)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = np.zeros(N-1, np.int64)

for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        ans[min(d1, d2) - 1] += 1

[print(ans[i]) for i in range(N - 1)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = [0] * (N-1)

c = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        d3 = abs(Y - i) + 1 + abs(j - X)
        ans[min(d1, d2, d3) - 1] += 1

[print(ans[i]) for i in range(N - 1)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = np.zeros(N-1, np.int64)

c = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        d3 = abs(Y - i) + 1 + abs(j - X)
        ans[min(d1, d2, d3) - 1] += 1

[print(ans[i]) for i in range(N - 1)]

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

ans = []

for k in range(N - 1):
    c = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            d1 = abs(j - i)
            d2 = abs(X - i) + 1 + abs(j - Y)
            d3 = abs(Y - i) + 1 + abs(j - X)
            dist = min(d1, d2, d3) - 1
            if dist == k:
                c += 1
    ans.append(c)

[print(ans[i]) for i in range(N - 1)]

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = list(map(int,input().split()))
for i in range (1,N):
    a = max(N - 1 - (Y - X - 1) - (i - 1),0)
    if Y - X + 1 > 2 * i:
        b = Y - X + 1
        if i == 1:
            b = b - 1
    elif Y - X + 1 == 2 * i:
        b = i
    else:
        b = 0
    c = 0
    for j in range (1,X):
        if  i - (X - j) < 1:
            c = c
        elif i - (X - j)== 1:
            c = c + 1
        elif 2 * (i - (X - j)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (X - j)) == Y - X + 1:
            c = c + 1
    for j in range(Y + 1,N + 1):
        if i - (j - Y)  < 1:
            c = c
        elif i - (j - Y) == 1:
            c = c + 1
        elif 2 * (i - (j - Y)) < Y - X + 1:
            c = c + 2
        elif 2 * (i - (j - Y)) == Y - X + 1:
            c = c + 1
        
    print(a+b+c)

Submission status: Time Limit Exceeded

Solution code:
# from sys import stdin

# # 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


# if __name__ == '__main__':
#     data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
#     get_result(data)

from sys import stdin
from collections import deque


# 重みなしグラフの隣接リスト
# 0-indexed nodes
def get_adj_list(num_nodes, data, undirected=True):
    graph = [[] for _ in range(num_nodes)]
    for val in data:
        x, y = val
        graph[x-1] = graph[x-1] + [y-1]
        if undirected:
            graph[y-1] = graph[y-1] + [x-1]
    return graph


# BFS
def breadth_first_search(adj_list, start_node):
    N = len(adj_list)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while q:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num
            parent[v] = p
            depth[v] = d
            num += 1
            for u in adj_list[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth

# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, depth = breadth_first_search(adj_list, i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Time Limit Exceeded

Solution code:
K,X,Y = (int(x) for x in input().split())
num = K*(K-1)/2
distance = [0] *int(num)
ct = 0
for i in range(1,K):
    for j in range (i+1,K+1):
            distance[ct] = min(j-i,abs(i-X)+abs(j-Y)+1)
            ct += 1
for k in range (1,K):
    print(distance.count(k))

Submission status: Time Limit Exceeded

Solution code:
K,X,Y = (int(x) for x in input().split())
# distance = [[0] * K for i in range(K-1)]
distance = [0] *( K *(K-1))
ct = 0
for i in range(1,K):
    for j in range (i+1,K+1):
        if i < j:
            distance[ct] = min(j-i,abs(i-X)+abs(j-Y)+1)
            ct += 1
for k in range (1,K):
    print(distance.count(k))

Submission status: Time Limit Exceeded

Solution code:
K,X,Y = (int(x) for x in input().split())
distance = [0] *( K *(K-1))
ct = 0
for i in range(1,K+1):
    for j in range (1,K+1):
        if i < j:
            distance[ct] = min(j-i,abs(i-X)+abs(j-Y)+1)
            ct += 1
for k in range (1,K):
    print(distance.count(k))

Submission status: Time Limit Exceeded

Solution code:
n, x, y = list(map(int,input().split()))
d = [0 for i in range(1,n)] 
for i in range(1,n+1):
  for j in range(1,n+1):
    if i < j:
      d[min([j-i, abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)])-1] += 1

for i in d:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def dijkstra(s,n,cost):
    d = [float("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

N, X, Y = map(int, input().split())
cost = [[float('inf')]*N for _ in range(N)]
for i in range(1,N):
    cost[i-1][i] = 1
    cost[i][i-1] = 1
for i in range(N):
    cost[i][i] = 0
cost[X-1][Y-1] = 1
cost[Y-1][X-1] = 1

d = [0]*N
for i in range(N):
    tmp = dijkstra(i,N,cost)
    for j in tmp:
        if j != float('inf'):
            d[j] += 1

for i in range(1,N):
    print(d[i]//2)

Submission status: Time Limit Exceeded

Solution code:
def band(i, j, x, y):
  res = 0
  res = [j-i, abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)]
  return min(res)

d = {}
n, x, y = list(map(int,input().split()))
for i in range(1, n+1):
  for j in range(1, n+1):
    if i < j:
      #print(str(i)+','+str(j)+'  '+str(band(i, j, x, y)))
      if band(i, j, x, y) in d:
        d[band(i, j, x, y)] += 1
      else:
        d[band(i, j, x, y)] = 1
for i in range(1,n):
  if i in d:
    print(d[i])
  else:
    print('0')

Submission status: Time Limit Exceeded

Solution code:
def band(i, j, x, y):
  res = 0
  if i <= x and y <= j:#p1
    res += x - i
    res += 1
    res += j - y
  elif i <= x and j <= x:#p2
    res += j - i
  elif y <= i and y <= j:#p3
    res += j - i
  else:
    if i <= x and x <= j and j <= y:#p4
      res += band(i, x, x, y)
      if j - x <= y - j + 1:
        res += j - x
      else:
        res += y - j + 1
    elif x <= i and i <= y and y <= j:#p5
      if y - i <= i - x + 1:
        res += y - i
      else:
        res += i - x + 1
      res += band(y, j, x, y)
    elif x <= i and i <= y and x <= j and j <= y:#p6
      if j - i <= i - x + y - j + 1:
        res += j - i
      else:
        res += i - x + y - j + 1
  return res

d = {}
n, x, y = list(map(int,input().split()))
for i in range(1, n+1):
  for j in range(1, n+1):
    if i < j:
      #print(str(i)+','+str(j)+'  '+str(band(i, j, x, y)))
      if band(i, j, x, y) in d:
        d[band(i, j, x, y)] += 1
      else:
        d[band(i, j, x, y)] = 1
for i in range(1,n):
  if i in d:
    print(d[i])
  else:
    print('0')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    ans = [0] * N

    for i in range(N):
        approched = [False] * N

        que = deque([[i,0]])
        approched[i] = True

        while que:
            pos,distance = que.popleft()

            if pos + 1 < N and not approched[pos + 1]:
                que.append([pos + 1, distance + 1])
                approched[pos + 1] = True
                ans[distance + 1] += 1

            if pos - 1 >= 0 and not approched[pos - 1]:
                que.append([pos - 1, distance + 1])
                approched[pos - 1] = True
                ans[distance + 1] += 1

            if (pos == X - 1) and not approched[Y -1]:
                que.append([Y -1, distance + 1])
                approched[Y -1] = True
                ans[distance + 1] += 1

            if (pos == Y - 1) and not approched[X -1]:
                que.append([X -1, distance + 1])
                approched[X -1] = True
                ans[distance + 1] += 1

    for x in map(lambda x: x//2, ans[1:]):
        print(x)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def band(i, j, x, y):
  res = 0
  if i <= x and y <= j:#p1
    res += x - i
    res += 1
    res += j - y
  elif i <= x and j <= x:#p2
    res += j - i
  elif y <= i and y <= j:#p3
    res += j - i
  else:
    if i <= x and x <= j and j <= y:#p4
      res += band(i, x, x, y)
      if j - x <= y - j + 1:
        res += j - x
      else:
        res += y - j + 1
    elif x <= i and i <= y and y <= j:#p5
      if y - i <= i - x + 1:
        res += y - i
      else:
        res += i - x + 1
      res += band(y, j, x, y)
    elif x <= i and i <= y and x <= j and j <= y:#p6
      if j - i <= i - x + y - j + 1:
        res += j - i
      else:
        res += i - x + y - j + 1
  return res

d = {}
n, x, y = list(map(int,input().split()))
for i in range(1, n+1):
  for j in range(1, n+1):
    if i < j:
      #print(str(i)+','+str(j)+'  '+str(band(i, j, x, y)))
      if band(i, j, x, y) in d:
        d[band(i, j, x, y)] += 1
      else:
        d[band(i, j, x, y)] = 1
d2 = sorted(d.items())
for i in range(1,n):
  if i in d:
    print(d[i])
  else:
    print('0')

Submission status: Time Limit Exceeded

Solution code:
def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.pop(0)
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited


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

G = {}
G[0]=[1]

for i in range(n-1):
    G[i+1] = [i]
    if i==0:
        continue
    G[i].append(i+1)
G[x-1].append(y-1)
G[y-1].append(x-1)

dis_table=[]
for i in range(n):
    visited = [-1]*n
    queue = []
    visited[i]=0
    queue.append(i)
    dis_table.append(bfs(queue, visited))

ans = [0]*(n-1)
for i in range(1,n):
    for j in range(0,i):
        ans[dis_table[i][j]-1]+=1

for i in ans :
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
n,x,y = map(int,input().split())
g = [[]for i in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(1,n-1):
  g[i].append(i-1)
  g[i].append(i+1)
ans = [0]*(n-1)
def dfs(b,c):
  for i in g[b]:
    if a[i] > c+1:
      a[i] = c+1
      que.append([i,c+1])
    
for i in range(n):
  a = [999999999]*n
  a[i] = 0
  que = deque()
  que.append([i,0])
  while que:
    x,y = que.popleft()
    dfs(x,y)
  for j in a:
    if j == 0:
      continue
    ans[j-1] += 1
for i in ans:
  print(i//2)