Submission #21207034

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,Tk,Ao = gets.split.map(&:to_i)
C = Array.new(N+1){ [] }
E = $<.map{|ln|
  ln.split.map(&:to_i).tap{|a,b|
    C[a] << b
    C[b] << a
  }
}
D = [nil]*(N+1)
D[Tk] = -D[Ao] = 1
Q = Tk,Ao
while n = Q.shift
  d = D[n]+(D[n]<=>0)
  C[n].each{|c|
    next if D[c]
    D[c] = d
    Q << c
  }
end
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,Tk,Ao = gets.split.map(&:to_i)
C = Array.new(N+1){ [] }
E = $<.map{|ln|
	ln.split.map(&:to_i).tap{|a,b|
		C[a] << b
		C[b] << a
	}
}

D = [nil]*(N+1)
D[Tk] = -D[Ao] = 1
Q = Tk,Ao
while n = Q.shift
	d = D[n]+(D[n]<=>0)
	C[n].each{|c|
		next if D[c]
		D[c] = d
		Q << c
	}
end

tk,ao = E.find{|a,b| 1<(D[a]-D[b]).abs }.then{|a,b| D[a]<0 ? [a,b] : [b,a] }
dao = D[ao]-1

D.fill nil
D[tk] = D[ao] = dao
Q << tk
while n = Q.shift
	d = D[n]+1
	C[n].each{|c|
		next if D[c]
		D[c] = d
		Q << c
	}
end

p D.compact.max

Submission Info

Judge Result