126. Subway System

Codeforces

IDCF10269126

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You're going to a city that has a large subway system. The subway system has $n$ lines, and each line has a certain number of stations. However, some stations are "transfer stations": multiple lines go through them. Given a list of the stations that each subway line goes through, your task is to figure out how many transfer stations exist throughout the subway system. Note that "loop lines" that start and end at the same station may appear in the input, and stations that are the start and end of the loop but have no other lines going through them do *not* count as transfer stations. For a station to be a transfer station, it has to have multiple distinct lines going through it. The first line of input contains a single positive integer $n$: the number of lines in the subway system. The next $n$ test cases each consist of two lines of input. The first line consists of a single positive integer $m$: the number of stations in the given subway line The next line contains $m$ space-separated station names, representing the route of the given subway line. The subway line might be a loop line. Output a single positive integer $s$: the number of transfer stations in the subway system. Then, output $s$ station names: the name of each transfer station in the subway system, *in alphabetical order*. Can you figure out which city has the subway system described in the first test case? ## Input The first line of input contains a single positive integer $n$: the number of lines in the subway system.The next $n$ test cases each consist of two lines of input.The first line consists of a single positive integer $m$: the number of stations in the given subway lineThe next line contains $m$ space-separated station names, representing the route of the given subway line. The subway line might be a loop line. ## Output Output a single positive integer $s$: the number of transfer stations in the subway system. Then, output $s$ station names: the name of each transfer station in the subway system, *in alphabetical order*. [samples] ## Note Can you figure out which city has the subway system described in the first test case?

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of subway lines. For each line $ i \in \{1, \dots, n\} $, let $ S_i $ be a multiset of station names representing the stations on line $ i $. **Constraints** 1. $ n \geq 1 $ 2. Each $ S_i $ is a sequence (possibly with repeats due to loops) of station names. 3. A station is a *transfer station* if it appears in **at least two distinct lines** (i.e., $ |\{ i \mid s \in S_i \}| \geq 2 $). **Objective** Compute the set $ T = \left\{ s \mid \left| \left\{ i \mid s \in S_i \right\} \right| \geq 2 \right\} $. Output $ |T| $, followed by the elements of $ T $ sorted in alphabetical order.

API Response (JSON)

{
  "problem": {
    "name": "126. Subway System",
    "description": {
      "content": "You're going to a city that has a large subway system. The subway system has $n$ lines, and each line has a certain number of stations. However, some stations are \"transfer stations\": multiple lines g",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269126"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're going to a city that has a large subway system. The subway system has $n$ lines, and each line has a certain number of stations. However, some stations are \"transfer stations\": multiple lines g...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of subway lines.  \nFor each line $ i \\in \\{1, \\dots, n\\} $, let $ S_i $ be a multiset of station names representing the stations on line $ i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments