You are viewing a single comment's thread. Return to all comments →
To get the last test case (9) to work, I had to basically copy/paste the fgl library into the box:
{-# OPTIONS_GHC -O3 -threaded #-} import qualified Data.IntMap as IM import qualified Data.IntMap.Strict as IMS import qualified Data.Tree as T import Data.List(foldl') newtype Graph = Graph (IM.IntMap (IM.IntMap (), IM.IntMap ())) instance Show Graph where showsPrec d g = showParen (d > 10) $ showString "mkGraph " . shows (labNodes g) . showString " " . shows (labEdges g) mkGraph vs es = insEdges es $ Graph $ IM.fromList $ zip vs (repeat (IM.empty, IM.empty)) insEdges es g = foldl' insEdge g es insEdge (Graph g) (v, w) = g' `seq` Graph g' where g' = IM.adjust addP w $ IM.adjust addS v g addS (ps, ss) = (ps, IM.insert w () ss) addP (ps, ss) = (IM.insert v () ps, ss) labNodes (Graph g) = IM.keys g labEdges (Graph g) = do (node, (_, ss)) <- IM.toList g (next, _) <- IM.toList ss return (node, next) components :: Graph -> [[Int]] components = map T.flatten . (fixNodes xdff) fixNodes f g = f (labNodes g) g xdff vs g = fst (xdf vs g) xdf :: [Int] -> Graph -> ([T.Tree Int], Graph) xdf [] g = ([], g) xdf _ (Graph g) | IM.null g = ([], Graph g) xdf (v:vs) g = case match v g of (Nothing, g1) -> xdf vs g1 (Just (ps, node, ss), g1) -> (T.Node node ts:ts', g3) where (ts , g2) = xdf (ps ++ ss) g1 (ts', g3) = xdf vs g2 where match node (Graph g) = case IM.lookup node g of Nothing -> (Nothing, Graph g) Just (p, s) -> let !g1 = IM.delete node g !p' = IM.delete node p !s' = IM.delete node s !g2 = clearPred g1 node s' !g3 = clearSucc g2 node p' in (Just (IM.keys p', node, IM.keys s), Graph g3) clearSucc g v = IMS.differenceWith clearSucc' g clearSucc' (ps, ss) _ = Just (ps, IM.delete v ss) clearPred g v = IMS.differenceWith clearPred' g clearPred' (ps, ss) _ = Just (IM.delete v ps, ss) transportCost n links = sum $ map (ceiling . sqrt . fromIntegral . length) $ components $ mkGraph n links main = do n <- read <$> getLine _ <- getLine links <- pairUp . words <$> getContents print $ transportCost [1..n] links where pairUp [] = [] pairUp (x:[]) = [] pairUp (x:y:xs) = (read x, read y) : pairUp xs
Prison Transport
You are viewing a single comment's thread. Return to all comments →
To get the last test case (9) to work, I had to basically copy/paste the fgl library into the box: