codeforces-scrape

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

1857D.md (2447B)


      1 Source: https://codeforces.com/problemset/problem/1857/D
      2 
      3 D. Strong Vertices
      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 Given two arrays $a$ and $b$, both of length $n$. Elements of both arrays indexed from $1$ to $n$. You are constructing a directed graph, where edge from $u$ to $v$ ($u\neq v$) exists if $a_u-a_v \ge b_u-b_v$.
     22 
     23 A vertex $V$ is called strong if there exists a path from $V$ to all other vertices.
     24 
     25 A path in a directed graph is a chain of several vertices, connected by edges, such that moving from the vertex $u$, along the directions of the edges, the vertex $v$ can be reached.
     26 
     27 Your task is to find all strong vertices.
     28 
     29 For example, if $a=[3,1,2,4]$ and $b=[4,3,2,1]$, the graph will look like this:
     30 
     31  ![](https://espresso.codeforces.com/31f82f792a7fd3b26b5387a7e4d314077c73028c.png) The graph has only one strong vertex with number $4$
     32 
     33 Input
     34 
     35 The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains an integer $n$ ($2 \le n \le 2\cdot 10^5$) — the length of $a$ and $b$.
     38 
     39 The second line of each test case contains $n$ integers $a_1,a_2 \dots a_n$ ($-10^9 \le a_i \le 10^9$) — the array $a$.
     40 
     41 The third line of each test case contains $n$ integers $b_1,b_2 \dots b_n$ ($-10^9 \le b_i \le 10^9$) — the array $b$.
     42 
     43 It is guaranteed that the sum of $n$ for all test cases does not exceed $2\cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output two lines: in the first line, output the number of strong vertices, and in the second line, output all strong vertices in ascending order.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 4
     57 
     58 3 1 2 4
     59 
     60 4 3 2 1
     61 
     62 5
     63 
     64 1 2 4 1 2
     65 
     66 5 2 3 3 1
     67 
     68 2
     69 
     70 1 2
     71 
     72 2 1
     73 
     74 3
     75 
     76 0 2 1
     77 
     78 1 3 2
     79 
     80 3
     81 
     82 5 7 4
     83 
     84 -2 -3 -6
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 1
     91 4 
     92 2
     93 3 5 
     94 1
     95 2 
     96 3
     97 1 2 3 
     98 2
     99 2 3
    100 ```
    101 
    102 Note
    103 
    104 The first sample is covered in the problem statement.
    105 
    106 For the second sample, the graph looks like this:
    107 
    108  ![](https://espresso.codeforces.com/a3cbb2d5f186ed76ec3b0113eec3f8c120d9b505.png) The graph has two strong vertices with numbers $3$ and $5$. Note that there is a bidirectional edge between vertices $3$ and $5$. 
    109 
    110 In the third sample, the vertices are connected by a single directed edge from vertex $2$ to vertex $1$, so the only strong vertex is $2$.
    111 
    112 In the fourth sample, all vertices are connected to each other by bidirectional edges, so there is a path from every vertex to any other vertex.