結果

問題 No.556 仁義なきサルたち
ユーザー aimyaimy
提出日時 2017-08-24 18:54:34
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,705 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 151,552 KB
最終ジャッジ日時 2024-11-14 20:14:16
合計ジャッジ時間 1,226 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:2:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap.Strict’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
2 | import qualified Data.IntMap.Strict as M
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap.Strict as M
import Data.List

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

readInts :: B.ByteString -> [Int]
readInts = map readInt . B.words

readIntPair :: B.ByteString -> [(Int, Int)]
readIntPair = map (pair . map readInt . B.words) . B.lines

pair :: [t] -> (t, t)
pair [x, y] = (x, y)
pair _ = undefined

ordBy uf x y
  | rank uf x > rank uf y = x
  | rank uf x < rank uf y = y
  | rep uf x < rep uf y = x
  | otherwise = y

main = do
  [n,_] <- map read . words <$> getLine :: IO [Int]
  ms <- readIntPair <$> B.getContents
  mapM_ print (jingi n ms)

jingi n = sequence (map (flip rep) [1 .. n]) . foldl (\uf (a,b) -> merge uf a b) initial

untilFix :: Eq t => (t -> t) -> t -> t
untilFix f x = let x1 = f x in if x1 == x then x else untilFix f x1

data UnionFind = UnionFind {tree :: M.IntMap Point, rk :: M.IntMap Rank} deriving Show
type Point = Int  -- greater than 0
type Rank = Int

initial :: UnionFind
initial = UnionFind M.empty M.empty

rep :: UnionFind -> Point -> Point
rep uf p
  | M.notMember p (tree uf) = p
  | tree uf M.! p == p = p
  | otherwise = rep uf (tree uf M.! p)

rank :: UnionFind -> Point -> Rank
rank uf p = M.findWithDefault 1 (rep uf p) (rk uf)

merge :: UnionFind -> Point -> Point -> UnionFind
merge uf p q
  | same uf p q = uf
  | otherwise = UnionFind (M.insert rp2 rp1 (M.insert p2 rp1 (tree uf))) (M.insert rp1 (rk1 + rk2) (rk uf))
  where
    p1 = ordBy uf p q
    p2 = head (delete p1 [p,q])
    rp1 = rep uf p1
    rp2 = rep uf p2
    rk1 = rank uf p1
    rk2 = rank uf p2

same :: UnionFind -> Point -> Point -> Bool
same uf p1 p2 = rep uf p1 == rep uf p2
0