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  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  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.