Submission #38834722

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 Data.Array
import qualified Data.Set as S
main = do
  [t] <- bsGetLnInts
  replicateM_ t $ do
    [n,m] <- bsGetLnInts
    cs <- bsGetLnInts
    uvs <- replicateM m bsGetLnInts
    let ans = abc289e n m cs uvs
    print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc289e :: Int -> Int -> [Int] -> [[Int]] -> Int
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

import Data.Array
import qualified Data.Set as S

main = do
  [t] <- bsGetLnInts
  replicateM_ t $ do
    [n,m] <- bsGetLnInts
    cs <- bsGetLnInts
    uvs <- replicateM m bsGetLnInts
    let ans = abc289e n m cs uvs
    print ans

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

abc289e :: Int -> Int -> [Int] -> [[Int]] -> Int
abc289e n m cs uvs
  | cA ! 1 == cA ! n = -1
  | otherwise = loop 0 S.empty (S.singleton (1,n))
  where
    cA = listArray (1,n) cs
    g1 = accumArray (flip (:)) [] (1,n) -- 同色の頂点への辺のみのグラフ
         [p | (u:v:_) <- uvs, cA ! u == cA ! v, p <- [(u,v), (v,u)]]
    g2 = accumArray (flip (:)) [] (1,n) -- 色の異なる頂点間の辺のみのグラフ
         [p | (u:v:_) <- uvs, cA ! u /= cA ! v, p <- [(u,v), (v,u)]]
    loop cnt visited news
      | S.member (n,1) news = cnt
      | S.null news         = -1
      | otherwise           = loop (succ cnt) visited1 news1
      where
        visited1 = S.union visited news
        news1 = S.fromList $
          [ (c,d)
          | (a,b) <- S.elems news
          , c <- g1 ! a, d <- g1 ! b
          , S.notMember (c,d) visited1
          ] ++
          [ (c,d)
          | (a,b) <- S.elems news
          , c <- g2 ! a, d <- g2 ! b
          , S.notMember (c,d) visited1
          ]

Submission Info

Compile Error

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

Judge Result