Submission #140760

---

Source Code Expand

{-# LANGUAGE MultiParamTypeClasses,FlexibleContexts,FlexibleInstances,TypeSynonymInstances,BangPatterns,RankNTypes,TupleSections #-}
import Control.Monad
import Control.Monad.ST
import Control.Applicative
import Control.Arrow
import Debug.Trace
import Text.Printf

import Data.List
import Data.Int
import Data.Bits
import Data.Maybe
import Data.Array.Base
import Data.Array.Unboxed
import Data.Array.ST
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B

readInt = fromJust . fmap fst . B.readInt
readInts = map readInt . B.words <$> B.getLine
readIntPair = l2p . map readInt . take 2 . B.words <$> B.getLine
readLns :: Read a => IO [a]
readLns = map read . words <$> getLine
cmpFst (a,_) (b,_) = compare a b
cmpSnd (_,a) (_,b) = compare a b
cmpLen a b = length a `compare` length b
swap (a,b) = (b,a)
l2p (a:b:_) = (a,b)
p2l (a,b) = [a,b]
itof :: Int -> Double
itof = fromIntegral
defaultArray :: (IArray a e,Ix i) => e -> (i,i) -> [(i,e)] -> a i e
defaultArray = accumArray $ curry snd
flatten :: [(a,[(b,c)])] -> [((a,b),c)]
flatten = (=<<) $ uncurry $ fmap . first . (,)

main = do
    l <- map (l2p .map readInt. B.words) . B.lines <$> B.getContents
    let ((n1,m1):l1) = l
        (es1,((n2,m2):es2)) = splitAt m1 l1
    let d1 = dist n1 es1
        d2 = dist n2 es2
        rMax1 = maximum $ d1
        rMin1 = minimum $ d1
        rMax2 = maximum $ d2
        rMin2 = minimum $ d2
        rMin = maximum [rMax1,rMax2,rMin1 + rMin2 + 1]
        rMax = rMax1 + rMax2 + 1
    printf "%d %d\n" rMin rMax

inf :: Int
inf = 10^9

dist :: Int -> [(Int,Int)] -> [Int]
dist n es = do
    v <- [0..n-1]
    return $ runST $ do
        r <- newArray (0,n-1) True :: ST s (STUArray s Int Bool)
        unsafeWrite r v False
        go r 1 [v] []
    where
    g :: Array Int [Int]
    g = accumArray (flip (:)) [] (0,n-1) $ es ++ map swap es
    go r d [] [] = return (d-1)
    go r d [] !ns = go r (d+1) ns []
    go r d (v:vs) !ns = gosub (unsafeAt g v) ns
        where
        gosub [] !ns = go r d vs ns
        gosub (u:us) !ns = do
            b <- unsafeRead r u
            if b then do
                unsafeWrite r u False
                gosub us (u:ns)
            else
                gosub us ns

Submission Info

Judge Result