Submission #62346

ソースコード

?
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
36
37
38
39
40
41
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}
rev = []
count = 0
start = nil
goal = nil
n.times do |i|
n.times do |j|
if '#' != map[i][j]
rev << [i, j]
case map[i][j]
when 'S'
start = count
when 'G'
goal = count
end
count += 1
end
end
end
uf = UnionFind.new(rev.size)
rev.size.times do |_i|
i1, j1 = rev[_i]
(_i+1...rev.size).each do |_j|
i2, j2 = rev[_j]
if i1 == i2 or j1 == j2
uf.unite _i, _j
end
end
end
puts (uf.united?(start, goal) ? "Possible" : "Impossible")

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 32 ms 2136 KB
1
in02.txt AC 29 ms 2164 KB
1
in03.txt AC 29 ms 2196 KB
1
in04.txt AC 35 ms 2092 KB
1
in05.txt AC 22 ms 2124 KB
1
in06.txt AC 37 ms 2156 KB
1
in07.txt AC 18 ms 2180 KB
1
in08.txt AC 32 ms 2212 KB
1
in09.txt AC 23 ms 2244 KB
1
in10.txt AC 45 ms 2272 KB
1
in11.txt AC 24 ms 2268 KB
1
in12.txt AC 28 ms 2292 KB
1
in13.txt AC 34 ms 2324 KB
1
in14.txt AC 28 ms 2328 KB
1
in15.txt AC 25 ms 2344 KB
1
in16.txt AC 560 ms 2764 KB
1
in17.txt AC 94 ms 2296 KB
1
in18.txt AC 30 ms 2276 KB
1
in19.txt TLE 2000 ms 23224 KB
1
in20.txt AC 236 ms 2392 KB
1
in21.txt AC 27 ms 2304 KB
1
in22.txt AC 24 ms 2208 KB
1
in23.txt AC 410 ms 2748 KB
1
in24.txt AC 24 ms 2156 KB
1
in25.txt AC 1100 ms 2704 KB
1
in26.txt AC 24 ms 2200 KB
1
in27.txt AC 25 ms 2228 KB
1
in28.txt AC 48 ms 2252 KB
1
in29.txt AC 25 ms 2240 KB
1
in30.txt AC 31 ms 2392 KB
1
in31.txt AC 22 ms 2300 KB
1
in32.txt AC 25 ms 2328 KB
1
in33.txt AC 407 ms 2596 KB
1
in34.txt TLE 2000 ms 4956 KB
1
in35.txt AC 420 ms 2768 KB
1
in36.txt TLE 2000 ms 8016 KB
1
in37.txt TLE 2000 ms 7952 KB
1
in38.txt AC 804 ms 2840 KB
1
in39.txt TLE 2000 ms 10048 KB
1
in40.txt TLE 2000 ms 5364 KB
1
sample01.txt AC 26 ms 2428 KB
1
sample02.txt AC 25 ms 2464 KB
1