h624. 超級家教 YEE篇 - 高中生程式解題系統

內容

$l inmozhisong$ 有 $N$ 個家教學生（沒錯他就是這麼電）， $h a._.$ 是他的家教學生的其中之一，也是 $l inmozhisong$ 的ㄋㄩˇㄆㄥˊㄧㄡˇ。

但是在 $l inmozhisong$ 的學生裡面，存在著一種「抄抄抄」的風氣，常常會有人互相抄作業，使得 $l inmozhisong$ 很不高興。

他發現抄的方式有分成兩種：「小抄」及「大抄」。

像是前幾天才被他抓到， $k enkenken$ 「大抄」了 $b ecaido$ 的作業； $r 1cky$ 「大抄」了 $k enkenken$ 的作業；且 $r 1cky$ 也「小抄」了 $b ecaido$ 的作業， $l inmozhisong$ 稱他們這樣的抄襲關係為YEE關係（Yokunai yEe rElationship ）。

他又發現他的學生們很奇怪，他可以以某種方式將他們編號成 $1$ 到 $N$ ，然後對於編號 $i$ 的學生，他只會抄編號 $1$ 到 $i - 1$ 的學生的作業。

聰明的 $l inmozhisong$ 可以透過筆跡鑑定來找出哪些學生「小抄」了哪些學生的作業，但是「大抄」似乎就不好找了。

他研究了一番之後，發現了「大抄」的規則：若編號 $i$ 的學生「小抄」了編號 $j$ 的學生，且編號 $1$ 到 $i - 1$ 的學生都沒有人「小抄」了編號 $j$ 的學生，那編號 $i$ 的學生就是「大抄」了編號 $j$ 的學生。

給你 $l inmozhisong$ 觀察筆跡後列出的「小抄」名單，請問在這份名單中可以看出有多少的YEE關係存在呢？

輸入說明

輸入的第一行包含一個正整數 $N$ ，代表 $l inmozhisong$ 有 $N$ 個家教學生。

接著有 $N$ 行，每行包含( $M_{i} + 1$ )個正整數 $M_{i}, a_{(i, 1)}, a_{(i, 2)}, . . ., a_{(i, M_{i})}$ ，代表編號 $i$ 的學生「小抄」了編號 $a_{(i, 1)}, a_{(i, 2)}, . . ., a_{(i, M_{i})}$ 的學生的作業。

$1 \leq N \leq 10^{5}$

$0 \leq M_{i} \leq i - 1$

$\sum M_{i} \leq 10^{6}$

$1 \leq a_{(i, j)} \leq i - 1$

輸出說明

輸出一個正整數，代表共有多少的YEE關係。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 2.0s , <1K
公開測資點#1 (2%): 2.0s , <1K
公開測資點#2 (2%): 2.0s , <1K
公開測資點#3 (2%): 2.0s , <1K
公開測資點#4 (2%): 2.0s , <1K
公開測資點#5 (4%): 2.0s , <1K
公開測資點#6 (4%): 2.0s , <1K
公開測資點#7 (4%): 2.0s , <1K
公開測資點#8 (4%): 2.0s , <1K
公開測資點#9 (4%): 2.0s , <1K
公開測資點#10 (6%): 2.0s , <1M
公開測資點#11 (6%): 2.0s , <1M
公開測資點#12 (6%): 2.0s , <1M
公開測資點#13 (6%): 2.0s , <1K
公開測資點#14 (6%): 2.0s , <1M
公開測資點#15 (8%): 2.0s , <10M
公開測資點#16 (8%): 2.0s , <10M
公開測資點#17 (8%): 2.0s , <10M
公開測資點#18 (8%): 2.0s , <10M
公開測資點#19 (8%): 2.0s , <10M

提示：

$10 % ： N = 3$

$20 % ： N \leq 10$

$30 % ： N \leq 100$

$40 % ： N \leq 10^{5}$

$- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -$

在範例輸入#2中，我們可以以這張圖為示意圖，其中 $i$ 指向 $j$ 代表 $i$ 抄了 $j$ 的作業，並且以顏色來表示小抄（黑色+紅色）及大抄（紅色）。

其中符合YEE關係的的有：

4號大抄3號；3號大抄1號；4號小抄1號。

4號大抄3號；3號大抄2號；4號小抄2號。

$- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -$

h624與h625兩題的輸入測試資料完全相同，若測資太弱會再修改。

標籤:

出處:

臨末人，窩的超人 [管理者： Ststone1687 (Ststone) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」