codeforces-scrape

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

1143C.md (4190B)


      1 Source: https://codeforces.com/problemset/problem/1143/C
      2 
      3 C. Queen
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a rooted tree with vertices numerated from $1$ to $n$. A tree is a connected graph without cycles. A rooted tree has a special vertex named root.
     22 
     23 Ancestors of the vertex $i$ are all vertices on the path from the root to the vertex $i$, except the vertex $i$ itself. The parent of the vertex $i$ is the nearest to the vertex $i$ ancestor of $i$. Each vertex is a child of its parent. In the given tree the parent of the vertex $i$ is the vertex $p_i$. For the root, the value $p_i$ is $-1$.
     24 
     25  ![](https://espresso.codeforces.com/89dec5022cbf328500d1f0790b082548bea0349d.png) An example of a tree with $n=8$, the root is vertex $5$. The parent of the vertex $2$ is vertex $3$, the parent of the vertex $1$ is vertex $5$. The ancestors of the vertex $6$ are vertices $4$ and $5$, the ancestors of the vertex $7$ are vertices $8$, $3$ and $5$ 
     26 
     27 You noticed that some vertices do not respect others. In particular, if $c_i = 1$, then the vertex $i$ does not respect any of its ancestors, and if $c_i = 0$, it respects all of them.
     28 
     29 You decided to delete vertices from the tree one by one. On each step you select such a non-root vertex that it does not respect its parent and none of its children respects it. If there are several such vertices, you select the one with the smallest number. When you delete this vertex $v$, all children of $v$ become connected with the parent of $v$.
     30 
     31  ![](https://espresso.codeforces.com/b17235f5a5b36b832215da45c68b63ac46c8be7c.png) An example of deletion of the vertex $7$. 
     32 
     33 Once there are no vertices matching the criteria for deletion, you stop the process. Print the order in which you will delete the vertices. Note that this order is unique.
     34 
     35 Input
     36 
     37 The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of vertices in the tree.
     38 
     39 The next $n$ lines describe the tree: the $i$-th line contains two integers $p_i$ and $c_i$ ($1 \le p_i \le n$, $0 \le c_i \le 1$), where $p_i$ is the parent of the vertex $i$, and $c_i = 0$, if the vertex $i$ respects its parents, and $c_i = 1$, if the vertex $i$ does not respect any of its parents. The root of the tree has $-1$ instead of the parent index, also, $c_i=0$ for the root. It is guaranteed that the values $p_i$ define a rooted tree with $n$ vertices.
     40 
     41 Output
     42 
     43 In case there is at least one vertex to delete, print the only line containing the indices of the vertices you will delete in the order you delete them. Otherwise print a single integer $-1$.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 5
     51 3 1
     52 1 1
     53 -1 0
     54 2 1
     55 3 0
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 1 2 4
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 5
     68 -1 0
     69 1 1
     70 1 1
     71 2 0
     72 3 0
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 -1
     79 ```
     80 
     81 Input
     82 
     83 ```
     84 8
     85 2 1
     86 -1 0
     87 1 0
     88 1 1
     89 1 1
     90 4 0
     91 5 1
     92 7 0
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 5
     99 ```
    100 
    101 Note
    102 
    103 The deletion process in the first example is as follows (see the picture below, the vertices with $c_i=1$ are in yellow):
    104 
    105 * first you will delete the vertex $1$, because it does not respect ancestors and all its children (the vertex $2$) do not respect it, and $1$ is the smallest index among such vertices;
    106 * the vertex $2$ will be connected with the vertex $3$ after deletion;
    107 * then you will delete the vertex $2$, because it does not respect ancestors and all its children (the only vertex $4$) do not respect it;
    108 * the vertex $4$ will be connected with the vertex $3$;
    109 * then you will delete the vertex $4$, because it does not respect ancestors and all its children (there are none) do not respect it ([vacuous truth](https://en.wikipedia.org/wiki/Vacuous_truth));
    110 * you will just delete the vertex $4$;
    111 * there are no more vertices to delete.
    112 
    113  ![](https://espresso.codeforces.com/a3dcf36566d51f5dae247287bb42659885b915ff.png) 
    114 
    115 In the second example you don't need to delete any vertex:
    116 
    117 * vertices $2$ and $3$ have children that respect them;
    118 * vertices $4$ and $5$ respect ancestors.
    119 
    120  ![](https://espresso.codeforces.com/b70045a29a78d8bae48864eb9902be93484c9411.png) 
    121 
    122 In the third example the tree will change this way:
    123 
    124  ![](https://espresso.codeforces.com/114431666de59f2448f591836f19417bea14a508.png)