codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

787B.md (2833B)


      1 Source: https://codeforces.com/problemset/problem/787/B
      2 
      3 B. Not Afraid
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them.
     22 
     23 There are *n* parallel universes participating in this event (*n* Ricks and *n* Mortys). I. e. each of *n* universes has one Rick and one Morty. They're gathering in *m* groups. Each person can be in many groups and a group can contain an arbitrary number of members.
     24 
     25 Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility).
     26 
     27  ![](https://espresso.codeforces.com/8e28eeaa0567268e4a80f777c0a60c6bc0071709.png) 
     28 
     29 Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there's a group such that every member in that group is a traitor (they will plan and destroy the world).
     30 
     31 Summer knows that if there's a possibility that world ends (there's a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there's at least one scenario (among all 2*n* possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.
     32 
     33 Input
     34 
     35 The first line of input contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 104) — number of universes and number of groups respectively.
     36 
     37 The next *m* lines contain the information about the groups. *i*-th of them first contains an integer *k* (number of times someone joined *i*-th group, *k* > 0) followed by *k* integers *v**i*, 1, *v**i*, 2, ..., *v**i*, *k*. If *v**i*, *j* is negative, it means that Rick from universe number  - *v**i*, *j* has joined this group and otherwise it means that Morty from universe number *v**i*, *j* has joined it.
     38 
     39 Sum of *k* for all groups does not exceed 104.
     40 
     41 Output
     42 
     43 In a single line print the answer to Summer's question. Print "YES" if she should cancel the event and "NO" otherwise.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 4 2  
     51 1 -3  
     52 4 -2 3 2 -3
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 YES
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 5 2  
     65 5 3 -2 1 -1 5  
     66 3 -5 2 5
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 NO
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 7 2  
     79 3 -1 6 7  
     80 7 -5 4 2 4 7 -3 4
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 YES
     87 ```
     88 
     89 Note
     90 
     91 In the first sample testcase, 1st group only contains the Rick from universe number 3, so in case he's a traitor, then all members of this group are traitors and so Summer should cancel the event.