Vector より List が早い（場合がある）

競プロ典型 90 問 83 日目 － Colorful Graph（★6）

import Control.Monad
import qualified Data.ByteString.Char8 as C
import Data.List
import Data.Vector ((!))
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed.Mutable as UM

main = ints >>= \[n,m] -> replicateM m ints >>= \es -> 
  readLn >>= \q -> replicateM q ints >>= sol n m es q 

ints = unfoldr (C.readInt . C.dropWhile (==' ')) <$> C.getLine

sol n m es q qs = do
  t <- UM.replicate (n+1) (0,1)
  c <- UM.replicate (n+1) 1
  let
    f :: (Int, [Int]) -> IO ()
    f (i,[x,y]) = do
      print =<< if p!x
        then
          UM.read c x
        else do
          (i0,y0) <- UM.read t x
          snd <$> foldM (\z -> (max z <$>) . UM.read t) (i0,y0) (g!x)
      UM.unsafeModify t (const (i,y)) x
      UM.unsafeModify c (const y) x
      mapM_ (UM.unsafeModify c (const y)) (g'!x)
  mapM_ f $ zip [1..] qs
  where
  g = buildG n $ concatMap (\[a,b] -> [(a,b),(b,a)]) es
  s = floor . sqrt . fromIntegral $ 2*m
  p = V.map ((>s) . length) g
  g' = V.map (filter (p!)) g

buildG n es = V.create $ do
  v <- VM.replicate (n+1) []
  forM_ es $ \(a,b) -> VM.unsafeModify v (b:) a
  return v