codeforces-scrape

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

1204C.md (3378B)


      1 Source: https://codeforces.com/problemset/problem/1204/C
      2 
      3 C. Anna, Svyatoslav and Maps
      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 The main characters have been omitted to be short.
     22 
     23 You are given a directed unweighted graph without loops with $n$ vertexes and a path in it (that path is not necessary simple) given by a sequence $p_1, p_2, \ldots, p_m$ of $m$ vertexes; for each $1 \leq i \lt m$ there is an arc from $p_i$ to $p_{i+1}$.
     24 
     25 Define the sequence $v_1, v_2, \ldots, v_k$ of $k$ vertexes as good, if $v$ is a subsequence of $p$, $v_1 = p_1$, $v_k = p_m$, and $p$ is one of the shortest paths passing through the vertexes $v_1$, $\ldots$, $v_k$ in that order.
     26 
     27 A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. It is obvious that the sequence $p$ is good but your task is to find the shortest good subsequence.
     28 
     29 If there are multiple shortest good subsequences, output any of them.
     30 
     31 Input
     32 
     33 The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of vertexes in a graph.
     34 
     35 The next $n$ lines define the graph by an adjacency matrix: the $j$-th character in the $i$-st line is equal to $1$ if there is an arc from vertex $i$ to the vertex $j$ else it is equal to $0$. It is guaranteed that the graph doesn't contain loops.
     36 
     37 The next line contains a single integer $m$ ($2 \le m \le 10^6$) — the number of vertexes in the path.
     38 
     39 The next line contains $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \le p_i \le n$) — the sequence of vertexes in the path. It is guaranteed that for any $1 \leq i \lt m$ there is an arc from $p_i$ to $p_{i+1}$.
     40 
     41 Output
     42 
     43 In the first line output a single integer $k$ ($2 \leq k \leq m$) — the length of the shortest good subsequence. In the second line output $k$ integers $v_1$, $\ldots$, $v_k$ ($1 \leq v_i \leq n$) — the vertexes in the subsequence. If there are multiple shortest subsequences, print any. Any two consecutive numbers should be distinct.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 4
     51 0110
     52 0010
     53 0001
     54 1000
     55 4
     56 1 2 3 4
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 3
     63 1 2 4
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 4
     70 0110
     71 0010
     72 1001
     73 1000
     74 20
     75 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 11
     82 1 2 4 2 4 2 4 2 4 2 4
     83 ```
     84 
     85 Input
     86 
     87 ```
     88 3
     89 011
     90 101
     91 110
     92 7
     93 1 2 3 1 3 2 1
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 7
    100 1 2 3 1 3 2 1
    101 ```
    102 
    103 Input
    104 
    105 ```
    106 4
    107 0110
    108 0001
    109 0001
    110 1000
    111 3
    112 1 2 4
    113 ```
    114 
    115 Output
    116 
    117 ```
    118 2
    119 1 4
    120 ```
    121 
    122 Note
    123 
    124 Below you can see the graph from the first example:
    125 
    126 ![](https://espresso.codeforces.com/3e0af0adb4ab1272fc9152aae8708228c6014c45.png)
    127 
    128 The given path is passing through vertexes $1$, $2$, $3$, $4$. The sequence $1-2-4$ is good because it is the subsequence of the given path, its first and the last elements are equal to the first and the last elements of the given path respectively, and the shortest path passing through vertexes $1$, $2$ and $4$ in that order is $1-2-3-4$. Note that subsequences $1-4$ and $1-3-4$ aren't good because in both cases the shortest path passing through the vertexes of these sequences is $1-3-4$.
    129 
    130 In the third example, the graph is full so any sequence of vertexes in which any two consecutive elements are distinct defines a path consisting of the same number of vertexes.
    131 
    132 In the fourth example, the paths $1-2-4$ and $1-3-4$ are the shortest paths passing through the vertexes $1$ and $4$.