Submission #35149001

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import qualified Data.Vector.Unboxed.Mutable as MUV
import Control.Applicative
import qualified Data.IntMap as IM
import Control.Monad.ST
main = do
  [n,m] <- bsGetLnInts
  xs <- bsGetLnInts
  ys <- bsGetLnInts
  abzs <- replicateM m bsGetLnInts
  let ans = abc270f n m xs ys abzs
  print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import qualified Data.Vector.Unboxed.Mutable as MUV
import Control.Applicative
import qualified Data.IntMap as IM

import Control.Monad.ST

main = do
  [n,m] <- bsGetLnInts
  xs <- bsGetLnInts
  ys <- bsGetLnInts
  abzs <- replicateM m bsGetLnInts
  let ans = abc270f n m xs ys abzs
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)

abc270f :: Int -> Int -> [Int] -> [Int] -> [[Int]] -> Int
abc270f n m xs ys abzs = minimum [c1,c2,c3,c4]
  where
    n1 = succ n
    n2 = succ n1
    bridges = sort [(z,(a,b)) | (a:b:z:_) <- abzs]
    airs = sort [(x,(i, 0)) | (i,x) <- zip [1..] xs]
    seas = sort [(y,(i,n1)) | (i,y) <- zip [1..] ys]
    ba = merge bridges airs
    c1 = if succ m < n then maxBound else sub n2 n bridges
    c2 = sub n2 n1 ba
    c3 = sub n2 n1 $ merge bridges seas
    c4 = sub n2 n2 $ merge ba seas

sub :: Int -> Int -> [(Int,(Int,Int))] -> Int
sub n cnt zabs = runST $
  do
    uf <- newUF n
    (cost, cnt1) <- foldM (\(cost, cnt) (z,(a,b)) -> do
      m <- uniteUF uf a b
      return $ if m then (cost + z, pred cnt) else (cost, cnt)
      ) (0, cnt) zabs
    return $ if cnt1 == 1 then cost else maxBound
  
------------------
-- @gotoki_no_joe
merge :: Ord a => [a] -> [a] -> [a]
merge xxs@(x:xs) yys@(y:ys) =
  case compare x y of
    EQ -> x : y : merge xs ys
    LT -> x : merge xs yys
    GT -> y : merge xxs ys
merge [] ys = ys
merge xs [] = xs

-- @gotoki_no_joe
type UnionFind s = MUV.MVector s Int

newUF :: Int -> ST s (UnionFind s)
newUF n = MUV.replicate n (-1)

getRoot :: UnionFind s -> Int -> ST s (Int, Int)
getRoot uf i = loop uf i []
  where
    loop uf i ks = do
      k <- MUV.read uf i
      if k >= 0 then loop uf k (i:ks) else do
        forM_ (drop 1 ks) (\k -> MUV.write uf k i)
        return (i, -k)

uniteUF :: UnionFind s -> Int -> Int -> ST s Bool
uniteUF uf i j = do
  (a, r) <- getRoot uf i
  (b, s) <- getRoot uf j
  if a == b then return False else
    if r >= s then do
      MUV.write uf a (negate $ r + s)
      MUV.write uf b a
      return True
    else do
      MUV.write uf b (negate $ r + s)
      MUV.write uf a b
      return True

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result