結果

問題 No.556 仁義なきサルたち
ユーザー こまるこまる
提出日時 2020-10-16 12:43:13
言語 Haskell
(9.8.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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