Submission #62348

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class UnionFind
Node = Struct.new(:p, :h)
def initialize(size); @p, @r = size.times.to_a, [0]*size; end
def unite(i, j); k, l = parent(i), parent(j); if @r[k] < @r[l]; @p[k] = l; @r[l] += 1 if @r[k] == @r[l]; else; @p[l] = k; end; end
def united?(i, j); parent(i) == parent(j); end
def parent(i); j = i; until i == @p[i]; j, i = i, @p[j] = @p[i]; end; i; end
end
n = gets.to_i
map = n.times.map {gets.chomp}
rows = n.times.map {[]}
cols = n.times.map {[]}
count = 0
start = nil
goal = nil
uf = UnionFind.new n*n
n.times do |i|
n.times do |j|
if '#' != map[i][j]
rows[i].each { |k| uf.unite k, count }
cols[j].each { |k| uf.unite k, count }
rows[i] << count
cols[j] << count
case map[i][j]
when 'S'
start = count
when 'G'
goal = count
end
count += 1
end
end
end
puts (uf.united?(start, goal) ? "Possible" : "Impossible")

ステータス

項目 データ
問題 1336 - Hokkaido
ユーザー名 magurofly
投稿日時 2020-08-16 22:34:15
言語 Ruby
状態 Time Limit Exceeded
得点 0
ソースコード長 901 Byte
最大実行時間 2000 ms
最大メモリ使用量 7932 KB

セット

セット 得点 Cases
1 ALL 0 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 30 ms 2008 KB
1
in02.txt AC 30 ms 2036 KB
1
in03.txt AC 24 ms 2184 KB
1
in04.txt AC 23 ms 2076 KB
1
in05.txt AC 35 ms 2100 KB
1
in06.txt AC 27 ms 4176 KB
1
in07.txt AC 26 ms 2124 KB
1
in08.txt AC 24 ms 2156 KB
1
in09.txt AC 23 ms 2184 KB
1
in10.txt AC 28 ms 2216 KB
1
in11.txt AC 23 ms 2176 KB
1
in12.txt AC 28 ms 2208 KB
1
in13.txt AC 28 ms 2356 KB
1
in14.txt AC 29 ms 2336 KB
1
in15.txt AC 24 ms 2336 KB
1
in16.txt AC 73 ms 2484 KB
1
in17.txt AC 37 ms 2324 KB
1
in18.txt AC 26 ms 2236 KB
1
in19.txt TLE 2000 ms 6868 KB
1
in20.txt AC 53 ms 2444 KB
1
in21.txt AC 23 ms 2248 KB
1
in22.txt AC 27 ms 2272 KB
1
in23.txt AC 61 ms 2556 KB
1
in24.txt AC 23 ms 2192 KB
1
in25.txt AC 98 ms 2736 KB
1
in26.txt AC 32 ms 2420 KB
1
in27.txt AC 22 ms 2292 KB
1
in28.txt AC 25 ms 2440 KB
1
in29.txt AC 24 ms 2392 KB
1
in30.txt AC 22 ms 2404 KB
1
in31.txt AC 26 ms 2432 KB
1
in32.txt AC 34 ms 2312 KB
1
in33.txt AC 61 ms 2548 KB
1
in34.txt AC 572 ms 4228 KB
1
in35.txt AC 58 ms 2648 KB
1
in36.txt TLE 2000 ms 7148 KB
1
in37.txt TLE 2000 ms 7168 KB
1
in38.txt AC 90 ms 2812 KB
1
in39.txt TLE 2000 ms 7932 KB
1
in40.txt AC 416 ms 7084 KB
1
sample01.txt AC 29 ms 2272 KB
1
sample02.txt AC 29 ms 2424 KB
1