codeforces-scrape

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

1476C.md (2615B)


      1 Source: https://codeforces.com/problemset/problem/1476/C
      2 
      3 C. Longest Simple Cycle
      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 You have $n$ chains, the $i$-th chain consists of $c_i$ vertices. Vertices in each chain are numbered independently from $1$ to $c_i$ along the chain. In other words, the $i$-th chain is the undirected graph with $c_i$ vertices and $(c_i - 1)$ edges connecting the $j$-th and the $(j + 1)$-th vertices for each $1 \le j \lt c_i$.
     22 
     23 Now you decided to unite chains in one graph in the following way:
     24 
     25 1. the first chain is skipped;
     26 2. the $1$-st vertex of the $i$-th chain is connected by an edge with the $a_i$-th vertex of the $(i - 1)$-th chain;
     27 3. the last ($c_i$-th) vertex of the $i$-th chain is connected by an edge with the $b_i$-th vertex of the $(i - 1)$-th chain.
     28 
     29  ![](https://espresso.codeforces.com/613fe2860119e785c44eb05d78a94ed40a480bea.png) Picture of the first test case. Dotted lines are the edges added during uniting process 
     30 
     31 Calculate the length of the longest simple cycle in the resulting graph.
     32 
     33 A simple cycle is a chain where the first and last vertices are connected as well. If you travel along the simple cycle, each vertex of this cycle will be visited exactly once.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     38 
     39 The first line of each test case contains the single integer $n$ ($2 \le n \le 10^5$) — the number of chains you have.
     40 
     41 The second line of each test case contains $n$ integers $c_1, c_2, \dots, c_n$ ($2 \le c_i \le 10^9$) — the number of vertices in the corresponding chains.
     42 
     43 The third line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_1 = -1$; $1 \le a_i \le c_{i - 1}$).
     44 
     45 The fourth line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($b_1 = -1$; $1 \le b_i \le c_{i - 1}$).
     46 
     47 Both $a_1$ and $b_1$ are equal to $-1$, they aren't used in graph building and given just for index consistency. It's guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.
     48 
     49 Output
     50 
     51 For each test case, print the length of the longest simple cycle.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 3
     59 4
     60 3 4 3 3
     61 -1 1 2 2
     62 -1 2 2 3
     63 2
     64 5 6
     65 -1 5
     66 -1 1
     67 3
     68 3 5 2
     69 -1 1 1
     70 -1 3 5
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 7
     77 11
     78 8
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, the longest simple cycle is shown below:
     84 
     85  ![](https://espresso.codeforces.com/885ee3b5d950985047e6c8aa0ad7bee22dbe8607.png) 
     86 
     87 We can't increase it with the first chain, since in such case it won't be simple — the vertex $2$ on the second chain will break simplicity.