190. Contact Tracing

Codeforces

IDCF10269190

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

During the coronavirus pandemic, your town is attempting to trace the origins of recent COVID-19 cases. You're given a list of people who had the disease, and who they got it from, and you're trying to find the names of "superspreaders". For this problem, we'll define a _superspreader_ as someone who gave at least three other people COVID-19. Given this information, your task is to figure out the names of all of the superspreaders in the town. The first line of input contains a single positive integer $n$: the number of people in the town. The next $n$ lines contain two space-separated strings: the name of each person, and the name of the person they got the coronavirus from. Exactly one person in the town will have "OTHER" (no quotes) as the person they got the disease from, indicating that this person got the disease from a different town. Output $k$ lines, where $k$ is the number of superspreaders in the town. On each line, print the name of each superspreader in the order they were given in the input. If there aren't any superspreaders in the town, output "NONE" (no quotes). ## Input The first line of input contains a single positive integer $n$: the number of people in the town.The next $n$ lines contain two space-separated strings: the name of each person, and the name of the person they got the coronavirus from. Exactly one person in the town will have "OTHER" (no quotes) as the person they got the disease from, indicating that this person got the disease from a different town. ## Output Output $k$ lines, where $k$ is the number of superspreaders in the town. On each line, print the name of each superspreader in the order they were given in the input.If there aren't any superspreaders in the town, output "NONE" (no quotes). [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of people. Let $ P = \{p_1, p_2, \dots, p_n\} $ be the set of person names. Let $ S: P \to P \cup \{\text{OTHER}\} $ be the transmission function, where $ S(p_i) $ is the name of the person from whom $ p_i $ contracted COVID-19. **Constraints** 1. Exactly one person $ p_j $ satisfies $ S(p_j) = \text{OTHER} $. 2. For all $ p_i \in P $, $ S(p_i) \in P \cup \{\text{OTHER}\} $. **Objective** Define the out-degree function $ d: P \to \mathbb{Z}_{\geq 0} $, where $ d(x) = |\{ p_i \in P \mid S(p_i) = x \}| $, i.e., the number of people who contracted the virus from $ x $. A person $ x \in P $ is a *superspreader* if $ d(x) \geq 3 $. Output the names of all superspreaders in the order they appear in the input. If no superspreaders exist, output "NONE".

API Response (JSON)

{
  "problem": {
    "name": "190. Contact Tracing",
    "description": {
      "content": "During the coronavirus pandemic, your town is attempting to trace the origins of recent COVID-19 cases. You're given a list of people who had the disease, and who they got it from, and you're trying ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269190"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "During the coronavirus pandemic, your town is attempting to trace the origins of recent COVID-19 cases.\n\nYou're given a list of people who had the disease, and who they got it from, and you're trying ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of people.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be the set of person names.  \nLet $ S: P \\to P \\cup \\{\\text{OTHER}\\} $ be the transmission ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments