DMOPC '13 Contest 3 P1 - Sharing is Caring

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 16M

Author:

FatalEagle

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$ ~N~ people numbered $1$ ~1~ to $N$ ~N~ who have an account on Googol Drive and $M$ ~M~ documents which are shared from person $p$ ~p~ to person $q$ ~q~ $(1 \le p, q \le N)$ ~(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$ ~q~.

Input Specification

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

The next $M$ ~M~ pairs of lines will each contain $p_i$ ~p_i~ and $q_i$ ~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$ ~Y~ $(1 \le Y \le N)$ ~(1 \le Y \le N)~, your number.

Output Specification

You are to output all documents that are "shared with you" (shared with person $Y$ ~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.

Constraints

Test Case Batch	Marks	Constraints
1 [5 cases]	40	$1 \le N \le 10; 0 \le M \le 10$ ~1 \le N \le 10; 0 \le M \le 10~
2 [3 cases]	20	$1 \le N \le 10; 0 \le M \le 100$ ~1 \le N \le 10; 0 \le M \le 100~
3 [3 cases]	20	$1 \le N \le 1\,000; 0 \le M \le 1\,000$
4 [3 cases]	20	$1 \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
2

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
1

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.

Comments

-7

tiger2018 commented on Nov. 5, 2017, 2:01 a.m.

Googol? isn't it supposed to be Google?

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

-4

Anix55 commented on March 17, 2016, 7:01 p.m.

does order matter?

3

AlanL commented on Oct. 29, 2017, 10:02 p.m.

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