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 heapq
import collections

N,X,Y = (int(i) for i in input().split())

graph = collections.defaultdict(list)
# X->Yの経路を追加
graph[X].append((1,Y))
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  if i >=X and i <= Y:
    graph[i+1].append((1,i))

# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}

  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))
  for j in range(i+1,N+1):
    min_cost = checked_node[j]
    ans[min_cost-1] += 1

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [[10**18 for i in range(n+1)] for j in range(n+1)]

kyori = [0] * (n+1)

for i in range(n):
    dst[i+1][i+1] = 0

#num = 1

for i in range(1,n):
    #num = 1
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[i][y] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[i][y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[i][x] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[i][x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[i][tmp+1] == 10**18:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[i][tmp-1] == 10**18:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp-1] = tmp_dst+1
        
        #num += 1
        #print(dst[i])
    #exit()
    #print(dst[i])
    for j in range(i+1,n+1):
        kyori[dst[i][j]] += 1
"""
#print(kyori)
print(dst)
exit()

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1
"""
#print(kyori)
#exit()

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections

N,X,Y = (int(i) for i in input().split())

graph = collections.defaultdict(list)
# X->Yの経路を追加
graph[X].append((1,Y))
graph[Y].append((1,X))
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  graph[i+1].append((1,i))

# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}

  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))
  for j in range(i+1,N+1):
    min_cost = checked_node[j]
    ans[min_cost-1] += 1

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections

N,X,Y = (int(i) for i in input().split())

graph = collections.defaultdict(list)
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  graph[i+1].append((1,i))
# X->Yの経路を追加
graph[X].append((1,Y))
graph[Y].append((1,X))

# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}

  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))
  for min_cost in checked_node.values():
    if min_cost != 0:
      ans[min_cost-1] += 1

for a in ans:
  print(a//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
minus = []
plus = []
for A in range(1,N):
    for B in range(A+1,N+1):
        if B - A > abs(X -A) + abs(Y - B) + 1:
            minus.append(B-A)
            plus.append(abs(X -A) + abs(Y - B) + 1)
for k in range(1,N):
    print(N - k - minus.count(k) + plus.count(k))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [[0 for i in range(n+1)] for j in range(n+1)]

kyori = [0] * (n+1)

#num = 1

for i in range(1,n):
    #num = 1
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[i][y] == 0:
                #kyori[tmp_dst+1] += 1
                dst[i][y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[i][x] == 0:
                #kyori[tmp_dst+1] += 1
                dst[i][x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[i][tmp+1] == 0:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[i][tmp-1] == 0:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp-1] = tmp_dst+1
        
        #num += 1
        #print(dst[i])
    #exit()
    #print(dst[i])

#print(kyori)
#print(dst)

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1

#print(kyori)
#exit()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [[0 for i in range(n+1)] for j in range(n+1)]

kyori = [0] * (n+1)

#num = 1

for i in range(1,n):
    num = 1
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[i][y] == 0:
                #kyori[tmp_dst+1] += 1
                dst[i][y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[i][x] == 0:
                #kyori[tmp_dst+1] += 1
                dst[i][x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[i][tmp+1] == 0:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[i][tmp-1] == 0:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[i][tmp-1] = tmp_dst+1
        
        num += 1
        #print(dst[i])
    #exit()
    #print(dst[i])

#print(kyori)
#print(dst)

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1

#print(kyori)
#exit()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        num=0
        Tovis=[start]
        kyori[start]=0
        visited=[]
        while Tovis:
            nex=Tovis.pop(0)
            visited.append(nex)
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    if v in visited:
                        continue
                    if  v in Tovis:
                        continue
                    Tovis.append(v)
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [[0 for i in range(n+1)] for j in range(n+1)]

kyori = [0] * (n+1)

#num = 1

for i in range(1,n):
    num = 1
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[i][y] == 0:
                kyori[tmp_dst+1] += 1
                dst[i][y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[i][x] == 0:
                kyori[tmp_dst+1] += 1
                dst[i][x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[i][tmp+1] == 0:
                q.put([tmp+1,tmp_dst+1])
                kyori[tmp_dst+1] += 1
                dst[i][tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[i][tmp-1] == 0:
                q.put([tmp-1,tmp_dst+1])
                kyori[tmp_dst+1] += 1
                dst[i][tmp-1] = tmp_dst+1
        
        num += 1
        #print(dst[i])
    #exit()
    #print(dst[i])

#print(kyori)
#print(dst)

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1

#print(kyori)
#exit()

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
d = {}
for i in range(1,n+1):
    for j in range(i+1,n+1):
        d[(i,j)] = 999999999999

for i in range(1,n+1):
    q = [i]
    cnt = 1
    somr = 1
    soma = 0
    m = [0]*(n)
    while(len(q) != 0):
        r = q.pop(0)
        somr = somr-1
        m[r-1] = 1
        if r == x:
            if m[y-1] == 0:
                #d[cnt] = d[cnt] + 1
                f = 0
                if i > y:
                    z = d[(y,i)]
                    f = 1

                else:
                    z = d[(i,y)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(y,i)] = cnt

                    else:
                        d[(i,y)] = cnt

                soma = soma + 1
                q.append(y)

        if r == y:
            if m[x-1] == 0:
                #d[cnt = d[cnt]+1
                f = 0
                if i > x:
                    z = d[(x, i)]
                    f = 1

                else:
                    z = d[(i, x)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(x, i)] = cnt

                    else:
                        d[(i, x)] = cnt

                soma = soma+1
                q.append(x)

        if r+1 < n+1:
            if m[r] == 0:
                #d[cnt] = d[cnt]+1
                f = 0
                if i > r+1:
                    z = d[(r+1, i)]
                    f = 1

                else:
                    z = d[(i, r+1)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(r+1, i)] = cnt

                    else:
                        d[(i, r+1)] = cnt

                q.append(r+1)
                soma = soma+1

        if r-1 > 0:
            if m[r-2] == 0:
                #d[cnt] = d[cnt]+1
                f = 0
                if i > r-1:
                    z = d[(r-1, i)]
                    f = 1

                else:
                    z = d[(i, r-1)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(r-1, i)] = cnt

                    else:
                        d[(i, r-1)] = cnt

                q.append(r-1)
                soma = soma+1

        if somr == 0:
            cnt = cnt+1
            somr = somr+soma
            soma = 0

h = [0]*(n-1)
for i in d:
    e = d[i]
    h[e-1] = h[e-1]+1

print(*h)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
d = {}
for i in range(1,n+1):
    for j in range(i+1,n+1):
        d[(i,j)] = 999999999999

for i in range(1,n+1):
    q = [i]
    cnt = 1
    somr = 1
    soma = 0
    m = [0]*(n)
    while(len(q) != 0):
        r = q.pop(0)
        somr = somr-1
        m[r-1] = 1
        if r == x:
            if m[y-1] == 0:
                #d[cnt] = d[cnt] + 1
                f = 0
                if i > y:
                    z = d[(y,i)]
                    f = 1

                else:
                    z = d[(i,y)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(y,i)] = cnt

                    else:
                        d[(i,y)] = cnt

                soma = soma + 1
                q.append(y)

        if r == y:
            if m[x-1] == 0:
                #d[cnt = d[cnt]+1
                f = 0
                if i > x:
                    z = d[(x, i)]
                    f = 1

                else:
                    z = d[(i, x)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(x, i)] = cnt

                    else:
                        d[(i, x)] = cnt

                soma = soma+1
                q.append(y)

        if r+1 < n+1:
            if m[r] == 0:
                #d[cnt] = d[cnt]+1
                f = 0
                if i > r+1:
                    z = d[(r+1, i)]
                    f = 1

                else:
                    z = d[(i, r+1)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(r+1, i)] = cnt

                    else:
                        d[(i, r+1)] = cnt

                q.append(r+1)
                soma = soma+1

        if r-1 > 0:
            if m[r-2] == 0:
                #d[cnt] = d[cnt]+1
                f = 0
                if i > r-1:
                    z = d[(r-1, i)]
                    f = 1

                else:
                    z = d[(i, r-1)]
                    f = 2

                if cnt < z:
                    if f == 1:
                        d[(r-1, i)] = cnt

                    else:
                        d[(i, r-1)] = cnt

                q.append(r-1)
                soma = soma+1

        if somr == 0:
            cnt = cnt+1
            somr = somr+soma
            soma = 0

h = [0]*(n-1)
for i in d:
    e = d[i]
    h[e-1] = h[e-1]+1

print(*h)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
edge=[]
for i in range(int(n)):
    tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
    edge.append(tmp)
edge[x-1][y-1]=1
edge[y-1][x-1]=1
step=[0]*n#ある歩数の点の選び方をカウントする
def bfs(start,graph,step):
    kyori={}#スタートからある点までの距離をある点をキーとして入れる
    num=0
    Tovis=[start]
    kyori[start]=0
    visited=[]
    while Tovis:
        nex=Tovis.pop(0)
        visited.append(nex)
        for v in range(len(graph[nex])):
            tmp=graph[nex][v]
            if tmp!=-1:
                if v in visited:
                    continue
                if  v in Tovis:
                    continue
                Tovis.append(v)
                kyori[v]=kyori[nex]+1#点ｖまでの距離はその前に通った点までの距離+1
                step[kyori[v]]+=0.5#i->j j->iの二回数えてしまうので
for i in range(n):
    bfs(i,edge,step)
for i in range(1,len(step)):
    print(int(step[i]))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
edge=[]
for i in range(int(n)):
    tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
    edge.append(tmp)
edge[x-1][y-1]=1
edge[y-1][x-1]=1
step=[0 for i in range(n)]#ある歩数の点の選び方をカウントする
def bfs(start,graph,step):
    kyori={}#スタートからある点までの距離をある点をキーとして入れる
    num=0
    Tovis=[start]
    kyori[start]=0
    visited=[]
    while Tovis:
        nex=Tovis.pop(0)
        visited.append(nex)
        for v in range(len(graph[nex])):
            tmp=graph[nex][v]
            if tmp!=-1:
                if v in visited:
                    continue
                if  v in Tovis:
                    continue
                Tovis.append(v)
                kyori[v]=kyori[nex]+1#点ｖまでの距離はその前に通った点までの距離+1
                step[kyori[v]]+=0.5#i->j j->iの二回数えてしまうので
for i in range(n):
    bfs(i,edge,step)
for i in range(1,len(step)):
    print(int(step[i]))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
edge=[]
for i in range(int(n)):
    tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
    edge.append(tmp)
edge[x-1][y-1]=1
edge[y-1][x-1]=1
step=[0 for i in range(n)]
def bfs(start,graph,step):
    kyori={}
    num=0
    Tovis=[start]
    kyori[start]=0
    visited=[]
    while Tovis:
        nex=Tovis.pop(0)
        visited.append(nex)
        for v in range(len(graph[nex])):
            tmp=graph[nex][v]
            if tmp!=-1:
                if v in visited:
                    continue
                if  v in Tovis:
                    continue
                Tovis.append(v)
                kyori[v]=kyori[nex]+1
                step[kyori[v]]+=0.5
    return kyori
for i in range(n):
    bfs(i,edge,step)
for i in range(1,len(step)):
    print(int(step[i]))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
ans = ddict(int)
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        ans[min(p1,p2,p3)] += 1
for n in range(1,N):
    print(ans[n])

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math #sqrt
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # deque
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n,x,y = map(int,input().split())
    x -= 1
    y -= 1
    ans = [0 for i in range(n)]
    for i in range(n):
        g = [INF for i in range(n)]
        q = queue.Queue()
        q.put(i)
        g[i] = 0
        while not q.empty():
            r = q.get()
            ans[g[r]] += 1
            if r-1>=0 and g[r-1]==INF:
                g[r-1] = g[r] + 1
                q.put(r-1)
            if r+1<n and g[r+1]==INF:
                g[r+1] = g[r] + 1
                q.put(r+1)
            if r==x and g[y]==INF:
                g[y] = g[r] + 1
                q.put(y)
            elif r==y and g[x]==INF:
                g[x] = g[r] + 1
                q.put(x)
    for i in range(1,n):
        print(ans[i]//2)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
matrix = [[0 for n in range(0,N)] for nn in range(0,N)]
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        matrix[n][i] = min(p1,p2,p3)
matrix_flatten = sum(matrix,[])
for n in range(1,N):
    print(matrix_flatten.count(n))

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math #sqrt
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # deque
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n,x,y = map(int,input().split())
    x -= 1
    y -= 1
    ans = [0 for i in range(n)]
    for i in range(n):
        g = [INF for i in range(n)]
        q = queue.Queue()
        q.put(i)
        g[i] = 0
        while not q.empty():
            r = q.get()
            ans[g[r]] += 1
            if r-1>=0 and g[r-1]==INF:
                g[r-1] = g[r] + 1
                q.put(r-1)
            if r+1<n and g[r+1]==INF:
                g[r+1] = g[r] + 1
                q.put(r+1)
            if r==x and g[y]==INF:
                g[y] = g[r] + 1
                q.put(y)
            if r==y and g[x]==INF:
                g[x] = g[r] + 1
                q.put(x)
    for i in range(1,n):
        print(ans[i]//2)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math #sqrt
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # deque
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n,x,y = map(int,input().split())
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        g = [INF] * n
        q = queue.Queue()
        q.put(i)
        g[i] = 0
        while not q.empty():
            r = q.get()
            ans[g[r]] += 1
            if r-1>=0 and g[r-1]==INF:
                g[r-1] = g[r] + 1
                q.put(r-1)
            if r+1<n and g[r+1]==INF:
                g[r+1] = g[r] + 1
                q.put(r+1)
            if r==x and g[y]==INF:
                g[y] = g[r] + 1
                q.put(y)
            if r==y and g[x]==INF:
                g[x] = g[r] + 1
                q.put(x)
    for i in range(1,n):
        print(ans[i]//2)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
G = ddict(list)
for n in range(1,N):
    G[n].append(n+1)
    G[n+1].append(n)
G[X].append(Y)
G[Y].append(X)
def check(A):
    ret = True
    for a in A:
        if a == 0:
            ret = False
    return ret
from collections import deque
matrix = [[0 for n in range(0,N+1)] for nn in range(0,N+1)]
for i in range(1,N+1):
    Q = deque([i])
    pre_matrix = [0 for i in range(0,N+1)]
    while Q:
        q = Q.popleft()
        for c in G[q]:
            if matrix[i][c] == 0 or matrix[i][c] > matrix[i][q]+1:
                matrix[i][c] = matrix[i][q]+1
                matrix[c][i] = matrix[i][q]+1
            Q.append(c)
        if check(matrix[i][1:]):
            break
ans = ddict(int)
for i in range(1,N+1):
    for ii in range(i+1,N+1):
        ans[matrix[i][ii]] += 1
for n in range(1,N):
    print(ans[n])

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

ans = [0]*n
inf = 18930432

for i in range(n):
  dist = [inf]*n
  queue = [] 
  
  def push(v, d):
    if(dist[v] != inf):
      return 
    dist[v] = d
    queue.append(v)
 
   
  push(i, 0);
  
  while(queue):
    v = queue.pop(0)
    d = dist[v]
    if v-1 >= 0:
      push(v-1, d+1) 
    if (v+1 < n):
      push(v+1, d+1)
    if v == x:
      push(y, d+1)
    if v == y:
      push(x, d+1)
  #print(dist)
  
  for j in range(n):
    ans[dist[j]] += 1
  #print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]

N, X, Y = LI()

dist = [[INF] * (N+1) for _ in range(N+1)]

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

for i in range(1, N):
    tmp = 0
    for d in dist:
        tmp += d.count(i)

    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
 
i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

n,x,y = i_l()
x -= 1
y -= 1
a = []

for i in range(n):
    for j in range(i+1, n):
        a.append(min(abs(i-j), abs(x-i)+1+abs(y-j), abs(y-j)+1+abs(y-i)))
for i in range(1, n):
    count = a.count(i)
    if count>0:
        print(count)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
# Using BFS
from collections import defaultdict, deque
import sys


def input():
    return sys.stdin.readline()


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.append(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = deque()
        push(i, 0, dist, q)
        while len(q) != 0:
            v = q.popleft()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# Using BFS
import queue
from collections import defaultdict
import sys


def input():
    return sys.stdin.readline()


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = queue.Queue()
        push(i, 0, dist, q)
        while not q.empty():
            v = q.get()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Ans=[]

i=1
while i<=N:
    j=i+1
    while j<=N:
        Ans.append(min(j-i,abs(X-i)+1+abs(j-Y)))
        j=j+1
    i=i+1

k=1
while k<=N-1:
    print(Ans.count(k))
    k=k+1

Submission status: Time Limit Exceeded

Solution code:
# Using BFS
import queue
from collections import defaultdict


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = queue.Queue()
        push(i, 0, dist, q)
        while not q.empty():
            v = q.get()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
edge=[]
for i in range(int(n)):
    tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
    edge.append(tmp)
edge[x-1][y-1]=1
edge[y-1][x-1]=1
def bfs(start,goal,graph):
    keiro={}
    Tovisit=[start]
    visited=[]
    while len(Tovisit)>0:
        #print(Tovisit)
        if goal in Tovisit:
            break      
        nex=Tovisit.pop(0)
        visited.append(nex)
        for v in range(len(graph[nex])):
            if graph[nex][v]!=-1:
                if v in visited:
                    continue
                if v in Tovisit:
                    continue
                Tovisit.append(v)
                keiro[v]=nex
    sum=0
    x=goal
    while x!=start:
        sum+=1
        x=keiro[x]
    return sum
for k in range(1,n):
    num=0
    for i in range(n):
        for j in range(i,n):
            if bfs(i,j,edge)==k:
                num+=1
    print(num)