TopCoder

Caido
Waimai

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

47.5% (28/59)

Tags

Description

糟了!國家有危機了!

今天軍營偵測到了敵人的來襲,在戰場的分佈圖恰好是由 N 個島嶼(編號 1N)和 M 條雙向橋樑所連接的情況下,我國已經派出了 A 團軍隊在各地待命,其中第 i 團軍隊位於編號第 xi 的島嶼、兵力為 ci 人;而敵國則是派出了 B 團軍隊在各地待命,其中第 i 團軍隊位於編號第 yi 的島嶼、兵力為 di 人。

對於這場戰爭,我國在兵力上有著十足的把握,絕對不會比對方少。但由於事出突然,軍營在攻打策略上有些混亂還無法好好整理出來,於是他們找上了身為資訊兵的你,希望你給出一套攻打敵國的策略來幫助國家取得勝利。

為了使得軍隊的移動流程更加清晰,他們希望你給出的策略是這樣的:你必須依序輸出若干組移動順序 ui,vi,pi,代表你要讓我國在島嶼 ui 的軍隊分流 pi 的兵力出來移動到島嶼 vi,該島嶼的軍隊在接受到事件後,便會開始進行移動。每次移動之後,島嶼 ui 的我國軍隊人數會減少 pi 人,且接下來可能會有三種事件發生:

  • 島嶼 vi 上沒有任何軍隊:並不會有特殊的事情發生。
  • 島嶼 vi 上有我國的軍隊 qi 人:該島嶼的我國軍隊人數增加至 pi+qi 人。
  • 島嶼 vi 上有敵國的軍隊 qi 人:若 qi>pi,則該島嶼的敵國軍隊人數減少至 qipi 人;若 qi<pi,則該島嶼的敵國軍隊將會消失,並留下 piqi 人的我國軍隊在該島嶼上;若 qi=pi,則該島嶼上將不會剩下任何一人。

軍營希望敵國的所有軍隊都被消滅得一乾二淨,並限制你至多只能執行 Qupper 次移動,你可以幫助軍營設計策略嗎?

Input Format

首行輸入五個整數 N,M,A,B,Qupper,代表島嶼數量、橋樑數量、我國的軍隊團數、敵國的軍隊團數以及你最多可以執行的移動次數。
接下來 M 行,每行兩個正整數 ui,vi,代表第 i 條橋樑連接著編號 uivi 的兩座島嶼。
再接下來 A 行,每行兩個正整數 xi,ci,代表我國第 i 團軍隊位於編號 xi 的島嶼,兵力為 ci
最後接著 B 行,每行兩個正整數 yi,di,代表敵國第 i 團軍隊位於編號 yi 的島嶼,兵力為 di
所有同一行的數字將以單一空格隔開。

Output Format

首行輸出一個整數 Q,代表你決定的攻打事件數量。
接下來 Q 行,每行三個整數 ui,vi,pi,代表你要讓我國在島嶼 ui 的軍隊分流 pi 的兵力出來移動到島嶼 vi
請注意,若你輸出的 Q 不是介於 [0,Qupper] 之間的整數、uivi 不是介於 [1,N] 之間的整數 、pi 不是正整數、島嶼 ui 上的我國軍隊人數小於 piuivi 之間沒有橋樑、uivi 相同或所有的攻打事件結束後敵國軍隊並沒有完全被消滅,都將被視為不合法的操作,會獲得 0分。否則即使我國軍隊被完全消滅,也會獲得 。
所有同一行的數字須以單一空格隔開。

Sample Input 1

3 2 1 1 2
1 2
2 3
1 2
3 1

Sample Output 1

2
1 2 2
2 3 2

Sample Input 2

5 5 3 2 6
1 2
2 3
2 4
3 4
3 5
1 8
2 3
4 2
3 4
5 9

Sample Output 2

6
2 3 3
4 3 2
3 5 1
1 2 8
2 3 8
3 5 8

Sample Input 3

4 3 1 3 3
1 2
1 3
1 4
1 100
2 8
3 7
4 6

Sample Output 3

3
1 2 8
1 3 7
1 4 6

Hints

測資限制:

  • 2N3×105
  • N1Mmin(N(N1)2,5×105)
  • 1A,BN
  • 2A+BN
  • N1Qupper3×105
  • 1ui,vi,xi,yiN
  • uivi
  • 沒有連接同樣兩座島嶼的兩座橋樑。
  • 1ci,di109
  • i=1Acii=1Bdi
  • 不會有兩團軍隊同時在同一座島嶼。
  • 保證任兩座島嶼都可以經由若干座橋樑互相來往。

本題共有 5 組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

  1. (21%) M=N1ui=ivi=i+1
  2. (18%) N500Qupper=3×105
  3. (14%) N500
  4. (23%) A=1
  5. (24%) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 3~10 M=N1ui=ivi=i+1 21
2 11~25 N500Qupper=3×105 18
3 11~43 N500 14
4 44~59 A=1 23
5 0~77 無額外限制。 24

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 5
1 2000 524288 65536 5
2 2000 524288 65536 5
3 2000 524288 65536 1 5
4 2000 524288 65536 1 5
5 2000 524288 65536 1 5
6 2000 524288 65536 1 5
7 2000 524288 65536 1 5
8 2000 524288 65536 1 5
9 2000 524288 65536 1 5
10 2000 524288 65536 1 5
11 2000 524288 65536 2 3 5
12 2000 524288 65536 2 3 5
13 2000 524288 65536 2 3 5
14 2000 524288 65536 2 3 5
15 2000 524288 65536 2 3 5
16 2000 524288 65536 2 3 5
17 2000 524288 65536 2 3 5
18 2000 524288 65536 2 3 5
19 2000 524288 65536 2 3 5
20 2000 524288 65536 2 3 5
21 2000 524288 65536 2 3 5
22 2000 524288 65536 2 3 5
23 2000 524288 65536 2 3 5
24 2000 524288 65536 2 3 5
25 2000 524288 65536 2 3 5
26 2000 524288 65536 3 5
27 2000 524288 65536 3 5
28 2000 524288 65536 3 5
29 2000 524288 65536 3 5
30 2000 524288 65536 3 5
31 2000 524288 65536 3 5
32 2000 524288 65536 3 5
33 2000 524288 65536 3 5
34 2000 524288 65536 3 5
35 2000 524288 65536 3 5
36 2000 524288 65536 3 5
37 2000 524288 65536 3 5
38 2000 524288 65536 3 5
39 2000 524288 65536 3 5
40 2000 524288 65536 3 5
41 2000 524288 65536 3 5
42 2000 524288 65536 3 5
43 2000 524288 65536 3 5
44 2000 524288 65536 4 5
45 2000 524288 65536 4 5
46 2000 524288 65536 4 5
47 2000 524288 65536 4 5
48 2000 524288 65536 4 5
49 2000 524288 65536 4 5
50 2000 524288 65536 4 5
51 2000 524288 65536 4 5
52 2000 524288 65536 4 5
53 2000 524288 65536 4 5
54 2000 524288 65536 4 5
55 2000 524288 65536 4 5
56 2000 524288 65536 4 5
57 2000 524288 65536 4 5
58 2000 524288 65536 4 5
59 2000 524288 65536 4 5
60 2000 524288 65536 5
61 2000 524288 65536 5
62 2000 524288 65536 5
63 2000 524288 65536 5
64 2000 524288 65536 5
65 2000 524288 65536 5
66 2000 524288 65536 5
67 2000 524288 65536 5
68 2000 524288 65536 5
69 2000 524288 65536 5
70 2000 524288 65536 5
71 2000 524288 65536 5
72 2000 524288 65536 5
73 2000 524288 65536 5
74 2000 524288 65536 5
75 2000 524288 65536 5
76 2000 524288 65536 5
77 2000 524288 65536 5