Problem : 134 - Driving Exam

Problem Statistics

Solved Member: 11　　Submission: 47　　User Tried: 13

Statement:

駕訓班裡有 n 條由南向北的單向道路組成，依序由 1 標號到 n，每條道路恰好長 m 公尺。在這些南北向的道路之間有 p 條單向東西向的道路，每條道路連接相鄰兩南北向的道路。

考試的內容就是讓學生選擇一條南北向道路的最南端當做起點，並往北端前進，中間若遇到橫向的道路可以隨意地轉彎，以最北端(距離為m)的地方當做終點。

*駕訓班的道路圖，其中 n=4, m=3, p=5

由於測驗內容非常無聊，從某特定的起點出發能到達的終點數非常少。駕訓班的主任決定再新增 k 條橫向的單向道路，使得能到達 n 種終點的起點數越多越好。

請你計算加 k 條橫向道路之後，最多能夠比以前多幾個起點能夠到達 n 種終點(即每條直線道路的最北端都有辦法到達)。

Input:Output:

第 1 行有 4 個整數n(2 ≤ n ≤ 100000),m,p(0 ≤ p ≤ 100000),k(1 ≤ m,k ≤ 100000)，以空格將數字兩兩分離，分別代表南北向的道路數、南北向道路的長度、東西向的道路數、以及想新增的道路數。
接下來的 p 行每行有 3 個整數 Ni,Mi,Di，代表有一條橫向的道路在離起點 Mi 的地方連接編號為 Ni,Ni+1 的兩條道路。若 Di=0，則這條道路是由西向東，若 Di=1 則代表這條路是由東向西。
其中 1 ≤ Ni < n; 0 ≤ Mi ≤ m; Di為0或1。

輸出只有一行，請輸出一行數字，代表加完 k 條道路之後最多能比未加的時候多幾個起點可以到達所有終點。

Sample Input:Sample Output:

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

HINT:

如圖，虛線為新增的路線，多了1,3兩個起點可以到達所有終點。

Source:

POI 14 Stage 3

Problem Setter

Nekosyndrome

Testdata:

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