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())
a = []

for i in range(1, n + 1):
    if i == 1:
        a.append([2])
    elif i == n:
        a.append([n - 1])
    else:
        a.append([i - 1, i + 1])
a[x - 1].append(y)
a[y - 1].append(x)

d = {}
for i in range(n - 1):
    d[i + 1] = 0

pair = set()
def solve(s):
    que = [a[s - 1]]
    visit = set()
    visit.add(s)
    depth = 0

    while que != []:
        depth += 1
        nn = que[0]
        que = que[1:]
        adj = []
        for i in nn:
            if i not in visit:
                if (i, s) not in pair:
                    d[depth] += 1
                    pair.add((s, i))
                adj = adj + a[i-1]
            visit.add(i)
        if adj != []:
            que.append(adj)

for i in range(n):
    solve(i + 1)

for i in range(n - 1):
    print(d[i + 1])

Submission status: Time Limit Exceeded

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

for i in range(1, n + 1):
    if i == 1:
        a.append([2])
    elif i == n:
        a.append([n - 1])
    else:
        a.append([i - 1, i + 1])
a[x - 1].append(y)
a[y - 1].append(x)

d = {}
for i in range(n - 1):
    d[i + 1] = 0

pair = set()

def solve(s):
    que = [a[s - 1]]
    visit = [s]
    depth = 0

    while que != []:
        depth += 1
        nn = que[0]
        que = que[1:]
        adj = []
        p = []
        for i in nn:
            if i not in visit:
                if (i, s) not in pair:
                    d[depth] += 1
                    pair.add((s, i))
                    p.append((s, i))
                adj = adj + a[i-1]
            visit.append(i)
        if adj != []:
            que.append(adj)

for i in range(n):
    solve(i + 1)

for i in range(n - 1):
    print(d[i + 1])

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

result = {x: 0 for x in range(N)}


def push(v, d, queue, dist):
    if v in dist:
        return
    dist[v] = d
    queue.appendleft(v)


def check(i):
    queue = deque()
    dist = {}
    push(i, 0, queue, dist)

    while queue:
        pos = queue.pop()
        d = dist[pos]

        if pos - 1 >= 0:
            push(pos - 1, d + 1, queue, dist)
        if pos + 1 < N:
            push(pos + 1, d + 1, queue, dist)
        if pos == X:
            push(Y, d + 1, queue, dist)
        if pos == Y:
            push(X, d + 1, queue, dist)

    for i in range(N):
        result[dist[i]] += 1


for i in range(N):
    check(i)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *


N, X, Y = MAP()

graph = [[] for _ in range(N)]

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

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

dic = defaultdict(int)
for i in range(N):
	q = deque([i])
	dist = [-1]*N
	dist[i] = 0

	while q:
		n = q.popleft()
		for node in graph[n]:
			if dist[node] == -1:
				dist[node] = dist[n] + 1
				q.append(node)

	for i in range(N):
		dic[dist[i]] += 1

for k in range(1, N):
	print(dic[k]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

def dijkstra(E, start): #最短経路のみ
	N_d = len(E)
	dist = [INF] * N_d
	dist[start] = 0
	q = [(0, start)]
	while q:
		dist_v, v = heappop(q)
		if dist[v] != dist_v:
			continue
		for u, dist_vu in E[v]:
			dist_u  = dist_v + dist_vu
			if dist[u] > dist_u:
				dist[u] = dist_u
				heappush(q, (dist_u, u))
	return dist	

N, X, Y = MAP()

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

dic = defaultdict(int)

ans = 0
for i in range(N):
	ans = dijkstra(graph, i)
	for key in ans:
		dic[key] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y=map(int,input().split())
l=[[1]]
for i in range(1,n-1):
    l.append([i-1,i+1])
l.append([n-2])
x,y=x-1,y-1
l[x].append(y)
l[y].append(x)
#print(l)
p=[0 for i in range(n)]
for j in range(n):
    s=[-1 for i in range(n)]
    s[j]=0
    q=deque([j])
    while len(q)>0:
        a=q.popleft()
        for i in l[a]:
            if s[i]==-1:
                s[i]=s[a]+1
                q.append(i)
    for i in s:
        if i!=0:
            p[i]+=1
print(*map(lambda x:x//2,p[1:]),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    N, X, Y = LI()
    X -= 1
    Y -= 1
    dist = [[N] * N for _ in range(N)]

    q = deque()
    for i in range(N):
        q.append(i)
        dist[i][i] = 0
        while q:
            u = q.popleft()
            if u < N - 1:
                if dist[i][u + 1] > dist[i][u] + 1:
                    q.append(u + 1)
                    dist[i][u + 1] = dist[i][u] + 1
            if u >= 1:
                if dist[i][u - 1] > dist[i][u] + 1:
                    q.append(u - 1)
                    dist[i][u - 1] = dist[i][u] + 1
            if u == X:
                if dist[i][Y] > dist[i][u] + 1:
                    q.append(Y)
                    dist[i][Y] = dist[i][u] + 1
            if u == Y:
                if dist[i][X] > dist[i][u] + 1:
                    q.append(X)
                    dist[i][X] = dist[i][u] + 1

    cnt = [0] * N

    for i in range(N):
        for j in range(i + 1, N):
            cnt[dist[i][j]] += 1

    for i in cnt[1:]:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    N, X, Y = LI()
    X -= 1
    Y -= 1
    dist = [[N] * N for _ in range(N)]

    for i in range(N):
        q = deque()
        q.append(i)
        dist[i][i] = 0
        while q:
            u = q.popleft()
            if u < N - 1:
                if dist[i][u + 1] > dist[i][u] + 1:
                    q.append(u + 1)
                    dist[i][u + 1] = dist[i][u] + 1
            if u >= 1:
                if dist[i][u - 1] > dist[i][u] + 1:
                    q.append(u - 1)
                    dist[i][u - 1] = dist[i][u] + 1
            if u == X:
                if dist[i][Y] > dist[i][u] + 1:
                    q.append(Y)
                    dist[i][Y] = dist[i][u] + 1
            if u == Y:
                if dist[i][X] > dist[i][u] + 1:
                    q.append(X)
                    dist[i][X] = dist[i][u] + 1

    cnt = [0] * N

    for i in range(N):
        for j in range(i + 1, N):
            cnt[dist[i][j]] += 1

    for i in cnt[1:]:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def bfs(n, g, start):
    d = [INF] * n
    que = deque([start])
    d[start] = 0
    while que:
        now = que.popleft()
        for next in g[now]:
            if d[next] != INF:
                continue
            que.append(next)
            d[next] = d[now] + 1
    return d


def main():
    n, x, y = LI()
    edges = defaultdict(list)
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
    for i in range(n - 1):
        edges[i].append(i + 1)
        edges[i + 1].append(i)
    ans = [0] * (n - 1)
    for i in range(n):
        d = bfs(n, edges, i)
        for k in range(1, n):
            ans[k - 1] += len([j for j in d if j == k])
    ans = list(map(lambda x: x//2, ans))
    print(*ans, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
x,y=x-1,y-1
adj=[[float("inf")]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        adj[i][j]=abs(i-j)
adj[x][y]=adj[y][x]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            adj[j][k]=min(adj[j][k],adj[j][i]+adj[i][k])
ans=[0 for i in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        ans[adj[i][j]]+=1
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1)
    adj[i+1].append(i)

ans = [0]*(n-1)
for i in range(n):
    q = deque([])
    q.append(i)

    dist = [-1]*n
    dist[i] = 0

    while len(q) > 0:
        v = q.popleft()
    
        for nv in adj[v]:
            if dist[nv] != -1:
                continue
        
            dist[nv] = dist[v] + 1
            q.append(nv)
    for i in dist:
        if i != 0:
            ans[i-1] += 1

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

Submission status: Time Limit Exceeded

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

for i in range(1, N+1):
  for j in range(i, N+1):
    dis.append(min(j-i, abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)))
    
for i in range(1, N):
  ans = dis.count(i)
  print(ans)

Submission status: Time Limit Exceeded

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

for k in range(1, N):
  ans = 0
  for i in range(1, N+1):
    for j in range(i, N+1):
      dis = min(j-i, abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X))
      if dis == k:
        ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
from itertools import chain
from collections import Counter
def main():
    def warshall_floyd(d):
        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])
        # 更新したdを返す。d[i][j]はノードiからノードjまでの最短距離
        # 行きつけないノードはinfになる。
        # 負閉路があるなら「ノードｖからノードｖへのコスト」、つまりd[x][x]がマイナス値になる。
        return d

    # 入力
    n, x, y = map(int, input().split())
    # ワーシャルフロイドで更新する変数dをつくる
    d = [[float("inf")] * n for _ in range(n)]
    d[x - 1][y - 1] = 1
    d[y - 1][x - 1] = 1
    for i1 in range(n-1):
        d[i1][i1+1] = 1
        d[i1+1][i1] = 1
    for j1 in range(n):
        d[j1][j1] = 0

    # ワーシャルフロイド実行。
    res = warshall_floyd(d)
    res1d = chain.from_iterable(res)
    res1dc = Counter(res1d)
    for i1 in range(1, n):
        r = res1dc[i1] // 2
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
def main():
    def warshall_floyd(d):
        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])
        # 更新したdを返す。d[i][j]はノードiからノードjまでの最短距離
        # 行きつけないノードはinfになる。
        # 負閉路があるなら「ノードｖからノードｖへのコスト」、つまりd[x][x]がマイナス値になる。
        return d

    # 入力
    n, x, y = map(int, input().split())
    # ワーシャルフロイドで更新する変数dをつくる
    d = [[float("inf")] * n for _ in range(n)]
    d[x - 1][y - 1] = 1
    d[y - 1][x - 1] = 1
    for i1 in range(n-1):
        d[i1][i1+1] = 1
        d[i1+1][i1] = 1
    for j1 in range(n):
        d[j1][j1] = 0

    # ワーシャルフロイド実行。
    res = warshall_floyd(d)
    r = [0] * (n - 1)
    for i1 in range(n-1):
        for i2 in range(i1 + 1, n):
            r[res[i1][i2] - 1] += 1
    print(*r, sep= '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
cnt_l = [0]*n
from collections import deque
def bfs(start):
    queue = deque()
    queue.append([start,0])
    isSearched = [False]*(n+1)
    
    while(len(queue)>0):
        i,cnt = queue.popleft()
        
        if(isSearched[i]):
            continue
        
        isSearched[i]=True
        cnt_l[cnt]+=1
        
        if(i==x):
            nex_l = (i-1,y,i+1)
        elif(i==y):
            nex_l = (i-1,x,i+1)
        else:
            nex_l = (i-1,i+1)

        for j in nex_l:
            if(j < 1 or n < j):
                continue
            if(isSearched[j]):
                continue
            queue.append([j,cnt+1])
            
        
 
        
for i in range(1,n+1):
    bfs(i)
 
 
for i in range(1,n):
    print(cnt_l[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
cnt_l = [0 for i in range(0,n)]
from collections import deque
def bfs(start):
    queue = deque()
    queue.append([start,0])
    isNotSearched = [False]*(n+1)
    
    while(len(queue)>0):
        i,cnt = queue.popleft()
        
        if(isNotSearched[i]):
            continue
        
        isNotSearched[i]=True
        cnt_l[cnt]+=1
        pre = (i-1)
        nex = (i+1)
        if(i==x):
            queue.append([y,cnt+1])
        if(i==y):
            queue.append([x,cnt+1])
        if(pre>=1):
            queue.append([pre,cnt+1])
        if(nex<=n):
            queue.append([nex,cnt+1])
            
        
 
        
for i in range(1,n+1):
    bfs(i)
 
 
for i in range(1,n):
    print(cnt_l[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,x,y = IL()
    x -= 1
    y -= 1
    dist = np.zeros(n-1,dtype='int32')
    for i in range(n):
        for j in range(i+1,n):
            tmp = min(abs(j-i),abs(j-x)+abs(x-i),abs(y-j)+abs(x-i)+1)
            dist[tmp-1] += 1
    for rep in dist:
        print(rep)
    return

if __name__=='__main__':
    Main()

Submission status: Time Limit Exceeded

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

adj = [[] for i in range(N)]
for i in range(N):
    if i != 0 and i != N-1:
        adj[i].append(i-1)
        adj[i].append(i+1)
    elif i == 0:
        adj[i].append(1)
    else:
        adj[i].append(N-2)
    if i == X-1:
        adj[i].append(Y-1)
    if i == Y-1:
        adj[i].append(X-1)

ans = [0 for i in range(N-1)]
for i in range(N):
    dist = [-1]*N
    st = deque([i])
    dist[i] = 0
    while st:
        l = st.pop()
        d = dist[l]
        for w in adj[l]:
            if dist[w] == -1:
                dist[w] = d+1
                st.append(w)
            elif dist[w] >= d+1:
                dist[w] = d + 1
                st.append(w)
    for k in range(1, N):
        ans[k-1] += dist.count(k)
for i in range(N-1):
    ans[i] = ans[i]//2
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

adj = [[] for i in range(N)]
for i in range(N):
    if i != 0 and i != N-1:
        adj[i].append(i-1)
        adj[i].append(i+1)
    elif i == 0:
        adj[i].append(1)
    else:
        adj[i].append(N-2)
    if i == X-1:
        adj[i].append(Y-1)
    if i == Y-1:
        adj[i].append(X-1)

ans = [0 for i in range(N-1)]
for i in range(N):
    dist = [-1]*N
    q = deque([i])
    dist[i] = 0
    while q:
        l = q.popleft()
        d = dist[l]
        for w in adj[l]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            q.append(w)
    for k in range(1, N):
        ans[k-1] += dist.count(k)
for i in range(N-1):
    ans[i] = ans[i]//2
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

adj = [[] for i in range(N)]
for i in range(N):
    if i != 0 and i != N-1:
        adj[i].append(i-1)
        adj[i].append(i+1)
    elif i == 0:
        adj[i].append(1)
    else:
        adj[i].append(N-2)
    if i == X-1:
        adj[i].append(Y-1)
    if i == Y-1:
        adj[i].append(X-1)

dists = []
for i in range(N):
    dist = [-1]*N
    q = deque([i])
    dist[i] = 0
    while q:
        l = q.popleft()
        d = dist[l]
        for w in adj[l]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            q.append(w)
    dists.append(dist)
ans = [0 for i in range(N-1)]
for i in range(N):
    for k in range(1, N):
        ans[k-1] += dists[i].count(k)
for i in range(N-1):
    ans[i] = ans[i]//2
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

adj = [[] for i in range(N)]
for i in range(N):
    if i != 0 and i != N-1:
        adj[i].append(i-1)
        adj[i].append(i+1)
    elif i == 0:
        adj[i].append(1)
    else:
        adj[i].append(N-2)
    if i == X-1:
        adj[i].append(Y-1)
    if i == Y-1:
        adj[i].append(X-1)
ans = []
for k in range(1, N):
    cur = 0
    for i in range(N):
        dist = [-1]*N
        q = deque([i])
        dist[i] = 0
        while q:
            l = q.popleft()
            d = dist[l]
            for w in adj[l]:
                if dist[w] > -1:
                    continue
                dist[w] = d + 1
                q.append(w)
        cur += dist.count(k)
    ans.append(cur//2)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
def bfs(target, graph, ans):
    visited = [False]*len(graph)
    que = Queue()
    que.put(target)
    visited[target] = True
    distance = [0]*len(graph)
    while not que.empty():
        root = que.get()
        for dst in graph[root]:
            if visited[dst] is False:
                visited[dst] = True
                que.put(dst)
                dist = distance[root] + 1
                distance[dst] = dist
                ans[dist-1] += 1 

n, x, y = map(int, input().split())
graph = {i:[] for i in range(n)}
for i in range(n-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[x-1].append(y-1)
graph[y-1].append(x-1)
ans = [0]*(n-1)
for target in range(n):
    bfs(target, graph, ans)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
N, X, Y = map(int, input().split())  # N個の頂点, XとYが繋がっている

graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
X -= 1
Y -= 1
graph[X].append(Y)
graph[Y].append(X)
# print(graph)

# 最後に//2すれば良い
ans = defaultdict(int)
for i in range(N):
    q = deque()
    # 開始のノード
    q.append(i)
    visited = [False]*N
    visited[i] = True
    distant = [100000] * N
    distant[i] = 0
    while len(q):
        v = q.popleft()
        for e in graph[v]:
            if visited[e]:
                continue
            distant[e] = distant[v] + 1
            ans[distant[e]] += 1
            visited[e] = True
            q.append(e)
    # 始点iからの幅優先探索完了
# print(ans)
for i in range(1, N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict


def main():
    N, X, Y = map(int, input().split())
    g = [[] for _ in range(N)]
    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)
    ans = defaultdict(int)

    for i in range(N):
        q = deque()
        q.append(i)
        visit_time = [0 for _ in range(N)]
        while len(q):
            v = q.popleft()
            time = visit_time[v]
            for j in g[v]:
                if visit_time[j] == 0 and j != i:
                    q.append(j)
                    visit_time[j] = time + 1
                else:
                    visit_time[j] = min(time + 1, visit_time[j])

        for v in visit_time:
            ans[v] += 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from sys import stdin
    def input():
        return stdin.readline().rstrip()
    def mips():
        return map(int,input().split())
    sys.setrecursionlimit(10**9)
    N,X,Y = mips()
    G = dict()
    for i in range(0,N):
        G[i] = []
    for i in range(0,N-1):
        G[i].append(i+1)
        G[i+1].append(i)
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)
    ans = [0 for _ in range(N)]
    #Question : for k = 1,...,N-1 : 
    #整数の組(i,j)(1≤i<j≤N)であって、Gにおいて頂点iと頂点jの最短距離がkであるようなものの数を求めてください
    def bfs(v,G,queue,dist):
        seen[v] = True
        for vertex in G[v]:
            if seen[vertex]:
                continue
            elif vertex in queue:
                continue
            queue.append(vertex)
            dist[vertex] = dist[v] + 1
        for elements in queue:
            queue.remove(elements)
            bfs(elements,G,queue,dist)
    for k in range(0,N):
        dist = [-1 for _ in range(N)]
        dist[k] = 0
        seen = [False for _ in range(N)]
        queue = []
        bfs(k,G,queue,dist)
        for el in dist:
            ans[el] += 1
    for i in range(1,N):
        print(ans[i]//2)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from sys import stdin
    def input():
        return stdin.readline().rstrip()
    def mips():
        return map(int,input().split())
    sys.setrecursionlimit(10**9)
    N,X,Y = mips()
    G = dict()
    for i in range(0,N):
        G[i] = []
    for i in range(0,N-1):
        G[i].append(i+1)
        G[i+1].append(i)
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)
    ans = [0 for _ in range(N)]
    #Question : for k = 1,...,N-1 : 
    #整数の組(i,j)(1≤i<j≤N)であって、Gにおいて頂点iと頂点jの最短距離がkであるようなものの数を求めてください
    def bfs(v,G,queue,dist):
        seen[v] = True
        for vertex in G[v]:
            if seen[vertex]:
                continue
            elif vertex in queue:
                continue
            queue.append(vertex)
            dist[vertex] = dist[v] + 1
        for elements in queue:
            queue.remove(elements)
            bfs(elements,G,queue,dist)
    for k in range(0,N):
        dist = [-1 for _ in range(N)]
        dist[k] = 0
        seen = [False for _ in range(N)]
        queue = []
        bfs(k,G,queue,dist)
        #print(dist)
        for j in range(1,N):
            a = dist.count(j)
            ans[j-1] += a
            if k == N-1:
                print(ans[j-1]//2)
    #for j in range(1,N):
        #print(ans[j-1]//2)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from sys import stdin
    def input():
        return stdin.readline().rstrip()
    def mips():
        return map(int,input().split())
    sys.setrecursionlimit(10**9)
    N,X,Y = mips()
    G = dict()
    for i in range(0,N):
        G[i] = []
    for i in range(0,N-1):
        G[i].append(i+1)
        G[i+1].append(i)
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)
    ans = [0 for _ in range(N)]
    #Question : for k = 1,...,N-1 : 
    #整数の組(i,j)(1≤i<j≤N)であって、Gにおいて頂点iと頂点jの最短距離がkであるようなものの数を求めてください
    def bfs(v,G,queue,dist):
        seen[v] = True
        for vertex in G[v]:
            if seen[vertex]:
                continue
            elif vertex in queue:
                continue
            queue.append(vertex)
            dist[vertex] = dist[v] + 1
        for elements in queue:
            queue.remove(elements)
            bfs(elements,G,queue,dist)
    for k in range(0,N):
        dist = [-1 for _ in range(N)]
        dist[k] = 0
        seen = [False for _ in range(N)]
        queue = []
        bfs(k,G,queue,dist)
        #print(dist)
        for j in range(1,N):
            a = dist.count(j)
            ans[j-1] += a
    for j in range(1,N):
        print(ans[j-1]//2)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
X -= 1
Y -= 1
aggre= [0] * (N - 1)

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    dist = min(abs(j - i),abs(X - i) + abs(Y - j) + 1,abs(Y - i) + abs(X - j) + 1)
    #if dist >= N // 2:
      #print("dist i j",dist,i,j)
    aggre[dist - 1] += 1
    
#ans = [i // 2 for i in aggre]
for a in aggre:
  print(a // 2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
X -= 1
Y -= 1
aggre= [0] * (N - 1)

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    dist = min(abs(j - i),abs(X - i) + abs(Y - j) + 1,abs(Y - i) + abs(X - j) + 1)
    #if dist >= N // 2:
      #print("dist i j",dist,i,j)
    aggre[dist - 1] += 1
    
ans = [i // 2 for i in aggre]
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, X, Y = map(int, input().split())
X -= 1; Y -= 1

pat = defaultdict(int)

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

for i in range(1, N):
  print(pat[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, X, Y = map(int, input().split())
X -= 1; Y -= 1
dist = []
for i in range(N):
  for j in range(i+1, N):
    dist.append(min([abs(i-j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)]))
    
pat = Counter(dist)

for i in range(1, N):
  print(pat[i])

Submission status: Time Limit Exceeded

Solution code:
#６回目、2020-0612
#2重ループ　＋O(1)
#i,jがループの中か外で場合分け

#初期入力
N, x, y = map(int, input().split())

ans ={i:[]for i in range(1,N)}
for i in range(1,N):
    for j in range(i+1,N+1):
         #（i,jがループより共に左、ともに右）
        if (j <=x or y <=i) :
            ans[j-i].append((i,j))
        # （iがループより左 and jがループより右）
        elif i <=x and y <=j:
            ans[x-i +1 +j-y].append((i,j))
        # i,jが共にループの中
        elif x <i and j <y:
            dist =min(j-i,i-x + y-j +1) #時計回りと反時計回りの短いほう、+1はxとyを結んだ部分
            ans[dist].append((i,j))
        # iがループより左、jがループの中
        elif i <=x and j < y:
            dist =x-i + min(j-x , y+1-j)
            ans[dist].append((i,j)) 
        # iがループの中、jがループの右
        elif x <i and y <=j:
            dist =min(y-i , 1 +i-x) + j-y
            ans[dist].append((i,j)) 

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