Problem : 321 - 看診問題

Problem Statistics

Solved Member: 13　　Submission: 34　　User Tried: 13

Statement:

現在有n 個病患收到了醫療中心的通知，. 每個人都收到了三種資訊：

　　• 每個人的號碼(依序由1, 2, ... , n 編號)
　　• 每個人應抵達醫療中心的時間點
　　• 一個關於他們檢查依序要去的房間編號順序列表

醫療中心的房間編號依序為1, 2, ... , m，而來到醫療中心做檢查的病患必須遵守下規則：

　　• 如果說病患應抵達醫療中心的時間為 t，那麼他會在時間 t 時抵達他的房間列表的第一間。
　　• 如果有多個病患同時抵達同個房間，他們會按照號碼由小到大排隊。若前面已有一個隊伍，則此時這個隊伍會接續在前一個隊伍後面。
　　• 如果說時間 t 時有隊伍在房間 x 前，隊伍中的第一個人將在時間t 進入房間做檢查，並且會在時間 t+1 時離開並（瞬間）移動至他房間列表中的下一個房間的隊伍裡。而隊伍中的下一個人將會於 t+1 的時間點進入房間x。
　　• 如果說病患在時間 t 進入房間 x 檢查，且這已經是他列表中的最後一個房間時，他將於 t+1 的時間點離開醫療中心。

你的任務是求出最後一個離開醫療中心的病患於何時離開。

Input:Output:

第一行有兩個整數n,m，表示病患數目與醫療中心的房間數目。

接下來有n行，每行會是：t_i, k_i, g_i,1, g_i,2, ... ,g_{i,k_i}，表示第i個病患應於時間t_i抵達醫療中心，房間列表共有k_i個，依序為g_i,1, g_i,2, ... ,g_{i,k_i}，此行所有整數將以空白隔開。

限制：
1 ≤ n,m ≤ 1000
0 ≤ t_i ≤ 1000000
k_i > 0
1 ≤ g_i,j≤ m
k₁ + k₂ + ... + k_n ≤ 100000

輸出一個數字，表示最後一個離開醫療中心的病患於何時離開。

Sample Input:Sample Output:

5 3
1 3 3 2 1
0 7 2 3 1 1 1 1 2
2 1 1
1 2 3 3
4 3 1 1 1

HINT:

Line 1：有5個人，醫院有3間診間
Line 2：編號1的人，在時間1來到醫院，依序要去3,2,1診間
Line 3：編號2的人，在時間0來到醫院，依序要去2,3,1,1,1,1,2診間
Line 4：編號3的人，在時間2來到醫院，依序要去1診間
Line 5：編號4的人，在時間1來到醫院，依序要去3,3診間
Line 6：編號5的人，在時間4來到醫院，依序要去1,1,1診間

Source:

102附中校內賽

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
2-1	1000ms	262144kb	10
2-2	1000ms	262144kb
2-3	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
3-3	1000ms	262144kb
4-1	1000ms	262144kb	10
4-2	1000ms	262144kb
5-1	1000ms	262144kb	10
5-2	1000ms	262144kb
6-1	1000ms	262144kb	10
6-2	1000ms	262144kb
7-1	1000ms	262144kb	10
7-2	1000ms	262144kb
7-3	1000ms	262144kb
7-4	1000ms	262144kb
8-1	1000ms	262144kb	10
8-2	1000ms	262144kb
8-3	1000ms	262144kb
9-1	1000ms	262144kb	10
9-2	1000ms	262144kb
9-3	1000ms	262144kb
10-1	1000ms	262144kb	10
10-2	1000ms	262144kb
10-3	1000ms	262144kb
10-4	1000ms	262144kb