{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ImportQualifiedPost #-}
{-# HLINT ignore "Use lambda-case" #-}
{-# LANGUAGE InstanceSigs #-}
{-# LANGUAGE LambdaCase #-}
{-# HLINT ignore "Used otherwise as a pattern" #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeApplications #-}
{-# OPTIONS_GHC -Wno-overlapping-patterns #-}
{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}
module Main where
import Control.Applicative ((<|>))
import Control.Monad
import Control.Monad.ST
import Control.Monad.State (MonadState (get), StateT (StateT, runStateT))
import Data.Array (Array)
import Data.Array.IArray
import Data.Array.IO
import Data.Array.IO.Internals (IOArray (IOArray), IOUArray (IOUArray))
import Data.Array.MArray
import Data.Array.ST ()
import Data.Array.ST.Safe (runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.Bifoldable (Bifoldable (bifold))
import Data.Bifunctor (bimap)
import Data.Bits (xor)
import Data.Bool (bool)
import Data.ByteString.Char8 qualified as BC
import Data.Char (digitToInt, ord)
import Data.Char qualified as C
import Data.Foldable (for_)
import Data.Foldable.Extra (traverse_)
import Data.Function (fix, on)
import Data.Graph.Inductive (deg', neighbors')
import Data.HashSet qualified as HS
import Data.Heap qualified as H
import Data.IORef (modifyIORef', newIORef, readIORef, writeIORef)
import Data.IORef qualified as MV
import Data.IntMap qualified as IM
import Data.IntSet qualified as IS
import Data.Ix
import Data.List
import Data.List.Extra
import Data.Map qualified as M
import Data.Maybe
import Data.Mutable
import Data.Ord
import Data.Ratio ((%))
import Data.STRef (modifySTRef', newSTRef, readSTRef, writeSTRef)
import Data.Sequence (Seq (Empty, (:<|), (:|>)), ViewL ((:<)), ViewR ((:>)), (|>))
import Data.Sequence qualified as Seq
import Data.Set qualified as S
import Data.Vector qualified as V
import Data.Vector.Algorithms.Intro qualified as VAI
import Data.Vector.Generic qualified as VG
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as MV
import Debug.Trace (traceShow)
import GHC.IO (unsafePerformIO)
import System.Environment (lookupEnv)
{-# RULES "Force inline VAI.sort" VAI.sort = VAI.sortBy compare #-}
main :: IO ()
main = do
n <- readLn @Int
abs <- zip [1 ..] <$> replicateM n getInts
let init = [i | (i, [a, b]) <- abs, a == 0, b == 0]
g = buildG (1, n) $ concat [[[a, i], [b, i]] | (i, [a, b]) <- abs, a /= 0, b /= 0]
ans = dfsRunSTUArray n (g !) init
print $ length $ findArrayIndices id ans
{-- lib --}
buildG :: (Int, Int) -> [[Int]] -> Array Int [Int]
buildG bounds edges = accumArray (flip (:)) [] bounds edges'
where
edges' = concatMap (\[u, v] -> [(u, v)]) edges
dfsRunSTUArray :: Int -> (Int -> [Int]) -> [Int] -> UArray Int Bool
dfsRunSTUArray n getNext initNodes = runSTUArray $ do
visited <- newArray (1, n) False
stackRef <- newSTRef initNodes
let loop = do
stack <- readSTRef stackRef
case stack of
[] -> return visited
(curr : rest) -> do
writeSTRef stackRef rest
isVisited <- readArray visited curr
if isVisited
then loop
else do
writeArray visited curr True
let neighbors = getNext curr
modifySTRef' stackRef (neighbors ++)
loop
loop
-- inputs
getInts :: IO [Int]
getInts = unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
getInteger :: IO [Integer]
getInteger = unfoldr (BC.readInteger . BC.dropWhile C.isSpace) <$> BC.getLine
-- outputs
printYn :: Bool -> IO ()
printYn f = putStrLn $ bool "No" "Yes" f
printList :: (Show a) => [a] -> IO ()
printList lst = putStrLn $ unwords $ map show lst
-- list
fromListToTuple :: [Int] -> (Int, Int)
fromListToTuple [a, b] = (a, b)
countBy :: (Foldable t) => (e -> Bool) -> t e -> Int
countBy predicate = foldl' (\acc a -> if predicate a then acc + 1 else acc) 0
-- fold
foldFor' :: (Foldable t) => b -> t a -> (b -> a -> b) -> b
foldFor' initial xs f = foldl' f initial xs
foldForM :: (Foldable t, Monad m) => b -> t a -> (b -> a -> m b) -> m b
foldForM initial xs m = foldM m initial xs
foldForM_ :: (Foldable t, Monad m) => b -> t a -> (b -> a -> m b) -> m ()
foldForM_ initial xs m = foldM_ m initial xs
-- Array用のfind
findArrayIndices :: (IArray a e, Ix i) => (e -> Bool) -> a i e -> [i]
findArrayIndices predicate as = [i | (i, e) <- assocs as, predicate e]
-- Array用の(!?)
(!?) :: (IArray a e, Ix i) => a i e -> i -> Maybe e
(!?) arr i =
let b = bounds arr
in if inRange b i
then Just (arr ! i)
else Nothing
instance (Num a, Num b) => Num (a, b) where
(+) :: (Num a, Num b) => (a, b) -> (a, b) -> (a, b)
(a1, b1) + (a2, b2) = (a1 + a2, b1 + b2)
(*) :: (Num a, Num b) => (a, b) -> (a, b) -> (a, b)
(a1, b1) * (a2, b2) = (a1 * a2, b1 * b2)
abs :: (Num a, Num b) => (a, b) -> (a, b)
abs (a1, b1) = (abs a1, abs b1)
signum :: (Num a, Num b) => (a, b) -> (a, b)
signum (a1, b1) = (signum a1, signum b1)
fromInteger :: (Num a, Num b) => Integer -> (a, b)
fromInteger i = (fromInteger i, fromInteger i)
negate :: (Num a, Num b) => (a, b) -> (a, b)
negate (a1, b1) = (negate a1, negate b1)
-- 符号なし32bit整数の限界値
maxUnsignedInt32 = 4294967295
minUnsignedInt32 = -4294967295
-- 符号つき32bit整数の最大値
minSignedInt32 = -2147483648
-- 符号なし64bit整数の限界値
-- 64bit
maxUnsignedInt64 = 18446744073709551615
minUnsignedInt64 = -18446744073709551615
-- 符号つき64bit整数の最大値
maxSignedInt64 = 9223372036854775807
{-- debug --}
dbg :: (Show a) => a -> ()
dbg _ = ()
fnDbg :: (Show a) => a -> a
fnDbg x = x
app/Main.hs:70:11: warning: [-Worphans]
Orphan rule: "Force inline VAI.sort"
forall (@(v :: * -> * -> *))
(@(m :: * -> *))
(@e)
($dPrimMonad_a96O :: PrimMonad m)
($dMVector_a96T :: Data.Vector.Generic.Mutable.Base.MVector v e)
($dOrd_a96U :: Ord e).
VAI.sort @m @v @e $dPrimMonad_a96O $dMVector_a96T $dOrd_a96U
= VAI.sortBy
@m @v @e $dPrimMonad_a96O $dMVector_a96T (compare @e $dOrd_a96U)
|
70 | {-# RULES "Force inline VAI.sort" VAI.sort = VAI.sortBy compare #-}
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:75:3: warning: [-Wname-shadowing]
This binding for ‘abs’ shadows the existing binding
imported from ‘Prelude’ at app/Main.hs:18:8-11
(and originally defined in ‘GHC.Num’)
|
75 | abs <- zip [1 ..] <$> replicateM n getInts
| ^^^
app/Main.hs:77:7: warning: [-Wname-shadowing]
This binding for ‘init’ shadows the existing binding
imported from ‘Data.List.Extra’ at app/Main.hs:51:1-22
(and originally defined in ‘GHC.List’)
|
77 | let init = [i | (i, [a, b]) <- abs, a == 0, b == 0]
| ^^^^
app/Main.hs:85:8: warning: [-Wname-shadowing]
This binding for ‘bounds’ shadows the existing binding
imported from ‘Data.Array.IArray’ at app/Main.hs:25:1-24
(and originally defined in ‘Data.Array.Base’)
|
85 | buildG bounds edges = accumArray (flip (:)) [] bounds edges'
| ^^^^^^
app/Main.hs:87:25: warning: [-Wincomplete-uni-patterns]
Pattern match(es) are non-exhaustive
In a lambda abstraction:
Patterns of type ‘[Int]’ not matched:
[]
[_]
(_:_:_:_)
|
87 | edges' = concatMap (\[u, v] -> [(u, v)]) edges
| ^^^^^^^^^^^^^^^^^^^
app/Main.hs:126:1: warning: [-Wincomplete-patterns]
Pattern match(es) are non-exhaustive
In an equation for ‘fromListToTuple’:
Patterns of type ‘[Int]’ not matched:
[]
[_]
(_:_:_:_)
|
126 | fromListToTuple [a, b] = (a, b)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:153:1: warning: [-Worphans]
Orphan instance: instance (Num a, Num b) => Num (a, b)
Suggested fix:
Move the instance declaration to the module of the class or of the type, or
wrap the type with a newtype and declare the instance on the new type.
|
153 | instance (Num a, Num b) => Num (a, b) where
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
app/Main.hs:168:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
maxUnsignedInt32 :: Integer
|
168 | maxUnsignedInt32 = 4294967295
| ^^^^^^^^^^^^^^^^
app/Main.hs:168:20: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from the literal ‘4294967295’
• In the expression: 4294967295
In an equation for ‘maxUnsignedInt32’:
maxUnsignedInt32 = 4294967295
|
168 | maxUnsignedInt32 = 4294967295
| ^^^^^^^^^^
app/Main.hs:170:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
minUnsignedInt32 :: Integer
|
170 | minUnsignedInt32 = -4294967295
| ^^^^^^^^^^^^^^^^
app/Main.hs:170:20: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from a use of syntactic negation
• In the expression: - 4294967295
In an equation for ‘minUnsignedInt32’:
minUnsignedInt32 = - 4294967295
|
170 | minUnsignedInt32 = -4294967295
| ^^^^^^^^^^^
app/Main.hs:173:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: minSignedInt32 :: Integer
|
173 | minSignedInt32 = -2147483648
| ^^^^^^^^^^^^^^
app/Main.hs:173:18: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from a use of syntactic negation
• In the expression: - 2147483648
In an equation for ‘minSignedInt32’: minSignedInt32 = - 2147483648
|
173 | minSignedInt32 = -2147483648
| ^^^^^^^^^^^
app/Main.hs:177:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
maxUnsignedInt64 :: Integer
|
177 | maxUnsignedInt64 = 18446744073709551615
| ^^^^^^^^^^^^^^^^
app/Main.hs:177:20: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from the literal ‘18446744073709551615’
• In the expression: 18446744073709551615
In an equation for ‘maxUnsignedInt64’:
maxUnsignedInt64 = 18446744073709551615
|
177 | maxUnsignedInt64 = 18446744073709551615
| ^^^^^^^^^^^^^^^^^^^^
app/Main.hs:179:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
minUnsignedInt64 :: Integer
|
179 | minUnsignedInt64 = -18446744073709551615
| ^^^^^^^^^^^^^^^^
app/Main.hs:179:20: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from a use of syntactic negation
• In the expression: - 18446744073709551615
In an equation for ‘minUnsignedInt64’:
minUnsignedInt64 = - 18446744073709551615
|
179 | minUnsignedInt64 = -18446744073709551615
| ^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:182:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: maxSignedInt64 :: Integer
|
182 | maxSignedInt64 = 9223372036854775807
| ^^^^^^^^^^^^^^
app/Main.hs:182:18: warning: [-Wtype-defaults]
• Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraint
Num a0 arising from the literal ‘9223372036854775807’
• In the expression: 9223372036854775807
In an equation for ‘maxSignedInt64’:
maxSignedInt64 = 9223372036854775807
|
182 | maxSignedInt64 = 9223372036854775807
| ^^^^^^^^^^^^^^^^^^^