結果

問題 No.556 仁義なきサルたち
コンテスト
ユーザー こまる
提出日時 2020-10-16 12:43:13
言語 Haskell
(9.10.1)
結果
WA  
実行時間 -
コード長 2,732 bytes
コンパイル時間 11,887 ms
コンパイル使用メモリ 207,616 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-07-20 20:29:40
合計ジャッジ時間 5,743 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

{-# LANGUAGE BangPatterns #-}

import           Control.Arrow
import           Control.Monad                     (liftM2, when)
import           Control.Monad.Fix                 (fix)
import           Data.IORef
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM

type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (second BSC8.tail) . BSC8.readInt
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  uf <- newUF n
  rep m $ \_ -> do
    (a, b) <- (\(vec1, vec2) -> (pred vec1, pred vec2)) <$> parse2
    p     <- rootUF uf a
    q     <- rootUF uf b
    sizeP <- sizeUF uf p
    sizeQ <- sizeUF uf q
    w <- newIORef (sizeP > sizeQ)
    when (sizeP == sizeQ) $ writeIORef w (p < q)
    check <- readIORef w
    if check
      then uniteUF uf p q
      else uniteUF uf q p
  rep n $ \i -> do
    dataI <- VUM.unsafeRead uf i
    if dataI < 0
      then print (i + 1)
      else print . succ =<< rootUF uf i

type UnionFind = VUM.IOVector Int

newUF :: Int -> IO UnionFind
newUF n = VUM.replicate n (-1)
{-# INLINE newUF #-}

rootUF :: UnionFind -> Int -> IO Int
rootUF uf x = do
  dataX <- VUM.unsafeRead uf x
  if dataX < 0
    then return x
    else do
      r <- rootUF uf dataX
      VUM.unsafeWrite uf x r
      return r
{-# INLINE rootUF #-}

connectedUF :: UnionFind -> Int -> Int -> IO Bool
connectedUF uf x y = liftM2 (==) (rootUF uf x) (rootUF uf y)
{-# INLINE connectedUF #-}

uniteUF :: UnionFind -> Int -> Int -> IO ()
uniteUF uf x y = do
  a <- rootUF uf x
  b <- rootUF uf y
  when (a /= b) $ do
    ar <- VUM.unsafeRead uf a
    br <- VUM.unsafeRead uf b
    let (p, c) = if ar < br then (a, b) else (b, a)
    when (ar == br) $ VUM.unsafeModify uf pred p
    VUM.unsafeWrite uf c p

connectGroupUF :: UnionFind -> IO Int
connectGroupUF uf = VU.length . VU.filter (>= 0) <$> VU.unsafeFreeze uf
{-# INLINE connectGroupUF #-}

sizeUF :: UnionFind -> Int -> IO Int
sizeUF uf = fix $ \loop x -> do
  px <- VUM.unsafeRead uf x
  if px < 0
    then return $! negate px
    else loop px
{-# INLINE sizeUF #-}

stream :: Monad m => Int -> Int -> VFSM.Stream m Int
stream !l !r = VFSM.Stream step l
  where
    step x
      | x < r     = return $ VFSM.Yield x (x + 1)
      | otherwise = return $ VFSM.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stream #-}

rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep n = flip VFSM.mapM_ (stream 0 n)
{-# INLINE rep #-}
0