← 返回题目列表

AtCoder · digitalarts_3

C. 绞肉机

中文机器翻译题面 查看原题

問題文

高桥先生是一位对安全感兴趣的年轻人,希望在 Digital Arts Inc. 找到一份工作。
他目前正在检查他运行的“推文型”SNS 的日志。
这个SNS被称为“Chokutter”,在一些有竞争力的程序员中很受欢迎。
“Chokutter”的规格说明如下。
  1. 您可以“发推文”短句。
    • 您的推文将显示在您的时间轴上。
  2. 您可以“关注”您以外的用户。
    • 当您关注某个用户A时,此后该用户A发布的所有推文都会显示在您的时间线上。您关注之前的推文将不会显示。
    • 在Chokutter上,如果您关注用户A,系统将强制用户A同时关注您。
    • 请注意,您关注的推文将同时显示在您和用户 A 的时间线上。
    • 您无法关注您已经关注的人或您自己。
  3. 您可以“取消关注”除您自己之外的用户。
    • 如果您取消关注某个用户A,则关注状态将被取消,取消关注后用户A的推文将不再显示在您的时间轴上。最初可见的推文将按原样显示。
    • 在Chokutter中,如果您取消关注用户A,系统将强制用户A同时取消关注您。
    • 由上可知,您取消关注的用户A的时间轴上将不再显示您的推文。
    • 您无法取消关注您不关注的人或您自己。
请注意,某些规格与类似服务不同。

Takahashi 希望根据 Chokutter 日志在用户自己的时间轴上显示的推文数量创建用户排名。 给出了
整数 K ,因此从上面的排名来看 请输出第 K 个用户的时间线上显示的推文数量。
在初始状态下,假设每个用户没有关注任何人。

入力

输入将以以下格式从标准输入提供。
N M K
s_{1}
s_{2}
:
:
s_{M}
  1. 1 行是一个表示用户数量的整数。 N(2≦N≦100,000) ,表示日志中行数的整数 M(0≦M≦100,000) 、整数 K(1≦K≦N) 由半角空格分隔。 跨
  2. 2 从行 M+1 至行 M 行记录 s_{i}(1≦i≦M) 。 来自行
  3. 日志 s_{i} 表示 3 它可以分为不同的格式。小于或等于的整数 j 和整数 k 是代表每个用户的数字, (1≦j, k≦N, j ≠ k)有保证。
    • s_{i} 的第一个字符是 t 什么时候
      • t j
        用户 j 的意思是“推文”。
    • s_{i} 的第一个字符是 f 什么时候
      • f j k
        用户 j 是用户 表示您已“关注” k 。 表示您已“取消关注”
    • s_{i} 的第一个字符是 u 什么时候
      • u j k
        用户 j 是用户 表示您已“关注” k 。

出力

按用户自己的时间轴上显示的推文数量从上到下排序。 输出第 K 个用户的时间线上显示的推文数量。
请在末尾输出换行符。

入力例 1

5 9 1
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 1

4
  • 见图a
    1. 首先,用户 1 发推文。由于此时没有人关注用户 1,因此只有用户 1 可以查看此推文。
  • 见图b
    1. 用户 1 随后关注用户 2 和用户 3。
    2. 用户 2 发推文。由于用户 1 是唯一关注用户 2 的人,因此该推文将出现在用户 1 和用户 2 的时间线上。
    3. 用户 1 发推文。由于用户 2 和用户 3 关注了用户 1,因此该推文将显示在用户 1、用户 2 和用户 3 的时间线上。
  • 见图c
    1. 用户 1 在用户 3 取消关注用户 1 后发布推文。该推文已被取消关注,因此仅出现在用户 1 和用户 2 的时间线上。
    2. 用户 5 随后发了两次推文。此推文仅在用户 5 的时间线上可见。
    3. 每个用户时间线上最终显示的推文数量为 4 用户 2 3 用户 3 1 用户 4 0 用户 5 2 一。
    4. 因此,在自己的时间轴上显示推文数量最多的用户是用户1,显示的推文数量是 4 就是答案。 由于除了

入力例 2

5 9 2
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 2

3
  • K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 2 推文数量最多的用户是用户2,显示的推文数量是 3 。

入力例 3

5 9 3
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 3

2
  • K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 3 数量最多的用户为用户5,显示推文条数为 2 。

入力例 4

5 9 4
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 4

1
  • K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 4 推文数量最多的用户是用户 3,显示的推文数量为 1 。

入力例 5

5 9 5
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 5

0
  • K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 5 最受欢迎的用户是用户 2,并且没有显示任何推文。

入力例 6

4 4 3
t 1
t 2
t 3
t 4

出力例 6

1
  • 4 一位用户时间轴上显示的推文总数为 1 所以,K 的值为 对于 1 它们的编号最大为 4 的任何值,要输出的答案是 1 。