DMOPC '13 Contest 3 P1 - Sharing is Caring

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

As the name implies, Googol Drive stores a vast amount of documents. So vast, in fact, that it would be impractical to manually search which documents are "shared with you" (and unfortunately, Googol does not support this operation yet). Given a list of N people numbered 1 to N who have an account on Googol Drive and M documents which are shared from person p to person q (1 \le p, q \le N), figure out which documents are "shared with you" — that is, you have direct access to such a document as person q.

Input Specification

The first line of input contains two integers, N and M.

The next M pairs of lines will each contain p_i and q_i on the first line, and the document title on the second line. You can assume that no document title is over 30 characters long.

The last line of input will be one integer Y (1 \le Y \le N), your number.

Output Specification

You are to output all documents that are "shared with you" (shared with person Y). The document names should each have their own line, and document names are case-sensitive. The order in which you output them does not matter, as long the list is correct as a whole.


Test Case BatchMarksConstraints
1 [5 cases]401 \le N \le 10; 0 \le M \le 10
2 [3 cases]201 \le N \le 10; 0 \le M \le 100
3 [3 cases]201 \le N \le 1\,000; 0 \le M \le 1\,000
4 [3 cases]201 \le N \le 1\,000\,000\,000; 0 \le M \le 10\,000

Sample Input 1

3 3
1 2
Road to Becoming a Philosopher
2 3
Hello, World
3 2
Untitled Document

Sample Output 1

Road to Becoming a Philosopher
Untitled Document

Explanation for Sample Output 1

Although all three documents are visible to you, you created the second one. Therefore, only two documents are "shared with you".

Sample Input 2

4 3
1 2
Chapter 15
1 3
Chapter 16
1 4
Chapter 16.5

Sample Output 2

(there is no output)

Explanation for Sample Output 2

No documents are "shared with you" — instead, you are the one sharing documents with others.


  • 1
    Orion222  commented on May 8, 2022, 2:03 a.m. edit 2

    how can i optimize memory?

    edit: fixed

  • -7
    tiger2018  commented on Nov. 4, 2017, 10:01 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.

  • -4
    Anix55  commented on March 17, 2016, 3:01 p.m.

    does order matter?

    • 3
      AlanL  commented on Oct. 29, 2017, 6:02 p.m.

      Order does not matter, it says so in the question.