Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
from queue import deque
q = deque([])
q.append(0)
ma = 0
while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Buggy python submission (verdict: Runtime Error):

AtCoder Beginner Contest 146
 日本語 
 sawakee (Guest) 
コンテスト時間: 2019-11-24(日) 21:00 ~ 2019-11-24(日) 22:40 (100分)AtCoderホームへ戻る
 トップ
 問題
 質問
 提出
 提出結果
 順位表
 バーチャル順位表
 コードテスト
 解説
D - Coloring Edges on Tree / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
400
 点

問題文
N
 頂点の木 
G
 が与えられます。 頂点には 
1
 から 
N
 までの番号がついており、
i
 本目の辺は頂点 
a
i
 と頂点 
b
i
 を結んでいます。

G
 の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。

上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 
1
 つ構築してください。

制約
2
≤
N
≤
10
5
1
≤
a
i
<
b
i
≤
N
入力はすべて整数
与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。

N

a
1
 
b
1

a
2
 
b
2

⋮

a
N
−
1
 
b
N
−
1

出力
出力は 
N
 行からなる。

1
 行目に使用する色の数 
K
 を出力せよ。

i
+
1
 行目 
(
1
≤
i
≤
N
−
1
)
 に 
i
 番目の辺の色を表す整数 
c
i
 を出力せよ。ここで 
1
≤
c
i
≤
K
 でなければならない。

問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。

入力例 1 
Copy
3
1 2
2 3
出力例 1 
Copy
2
1
2
入力例 2 
Copy
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
出力例 2 
Copy
4
1
2
3
4
1
1
2
入力例 3 
Copy
6
1 2
1 3
1 4
1 5
1 6
出力例 3 
Copy
5
1
2
3
4
5
言語
ソースコード
1
​
※ 512 KiB まで
※ ソースコードは「Main.拡張子」で保存されます




FacebookTwitterHatena共有
ルール 用語集
利用規約 プライバシーポリシー 個人情報保護方針 企業情報 よくある質問 お問い合わせ 資料請求
Copyright Since 2012 ©AtCoder Inc. All rights reserved.
 ページトップ

Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
import queue
q = queue.Queue()
q.put(0)
ma = 0
while not q.empty():
    nord = q.get()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.put(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
import queue
q = queue.Queue()
q.put(0)
ma = 0
while not q.empty():
    nord = q.get()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.put(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
g=[[] for i in range(n)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
for i in range(n-1):
	ab[i][0], ab[i][1] = ab[i][0]-1, ab[i][1]-1
	g[ab[i][0]].append(ab[i][1])
	g[ab[i][1]].append(ab[i][0])

ans=[[0 for i in range(n)]for j in range(n)]
from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

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


Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
g=[[] for i in range(n)]
ab=[]
for i in range(n-1):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	g[a].append(b)
	g[b].append(a)
	ab.append([a,b])

check=[False]*n
ans=[[0 for i in range(n)]for j in range(n)]

from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

print(ma)

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


Fixed submission:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)