Mock CCO '17 Day 2 P1 - Guards

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

imaxblue has sneaked into an Amestris military base and is waiting for Fuhrer King Bradley's arrival. But first, he must take care of the N guards. There are two types of guards, ones with bulletproof armour and ones with fireproof armour. imaxblue has two weapons, molotov cocktails and shotguns. Unfortunately, M pairs of guards are one-way friends with each other, therefore imaxblue must kill some guards before others. He would like to know the minimum number of times he needs to change weapons while following the order of friendships.

Input Specification

Line 1: N and M (N, M \le 200\,000)
Line 2: N integers, either 0 or 1, representing the type of each guard
Lines 3 \dots M+2: 2 integers a_i and b_i, representing that a_i must be killed before b_i
It is guaranteed that it will be possible to kill all guards. There may be multiple connections between the same pair.

Output Specification

Print on the first line the minimum number of times imaxblue is required to change his weapon.

Sample Input

6 4
0 1 0 1 1 1
0 1
3 2
1 2
2 5

Sample Output



  • -5
    Callum  commented on May 7, 2017, 8:53 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.