DWITE '11 R2 #5 - Portals Check

View as PDF

Submit solution

Points: 7
Time limit: 2.5s
Memory limit: 64M

Problem types
DWITE, November 2011, Problem 5

Scientists have finally discovered a method of creating a portal between two places (on Earth, as apparently the physics gets tricky when we get to space). Before mass producing their device the scientists want you to create software that checks whether two places are connected via a series of their portals. Help them with this project (Note: Portals are bidirectional, so they can be travelled through in both directions).

The input will contain 5 test sets. The first line of each set is a number 1 \le N \le 100\,000 representing the number of commands your software has to run, followed by N commands. Each command can be in one of the following two forms:

  • p\ a\ b – A portal joining a and b is added to the system. a and b are single words, no more than 255 characters each.
  • q\ a\ b – A query, asking if a and b are connected by any series of portals build so far. There will be at least one such query in each input set.

The output will contain 5 sets of outputs, answering each query command with connected or not connected.

Sample Input

p Waterloo Toronto
q Waterloo Toronto
p Dubai Toronto
p Montreal Vancouver
q Montreal Waterloo
p Dubai Vancouver
q Montreal Waterloo
q Waterloo Waterloo

Sample Output

not connected

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


  • 0
    maxcruickshanks  commented on Feb. 5, 2023, 2:21 a.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.