Submission #137893

---

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.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 $ elems d1
        rMin1 = minimum $ elems d1
        rMax2 = maximum $ elems d2
        rMin2 = minimum $ elems d2
        rMin = maximum [rMax1,rMax2,rMin1 + rMin2 + 1]
        rMax = rMax1 + rMax2 + 1
    printf "%d %d\n" rMin rMax

dist :: Int -> [(Int,Int)] -> UArray Int Int
dist n es = listArray (0,n-1) [ f v | v <- [0..n-1] ]
    where
    g :: Array Int [Int]
    g = accumArray (flip (:)) [] (0,n-1) $ es ++ map swap es
    f v = runST $ do
        r <- newArray (0,n-1) False
        go r [v] [] 0 0
    go :: STUArray s Int Bool -> [Int] ->  [Int] -> Int -> Int -> ST s Int
    go _ [] [] d !acc = return acc
    go vis [] ns d !acc = go vis ns [] (d+1) acc
    go vis (v:l) !ns !d !acc = do
        b <- readArray vis v
        if b then
            go vis l ns d acc
        else do
            writeArray vis v True
            let acc' = max acc d
                ns' = g ! v ++ ns
            go vis l ns' d acc'

Submission Info

Judge Result