TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

44.4% (24/54)

Tags

Description

糟了!國家有危機了!

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

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

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

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

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

Input Format

首行輸入五個整數 $N,M,A,B,Q_{upper}$,代表島嶼數量、橋樑數量、我國的軍隊團數、敵國的軍隊團數以及你最多可以執行的移動次數。
接下來 $M$ 行,每行兩個正整數 $u_i,v_i$,代表第 $i$ 條橋樑連接著編號 $u_i$ 和 $v_i$ 的兩座島嶼。
再接下來 $A$ 行,每行兩個正整數 $x_i,c_i$,代表我國第 $i$ 團軍隊位於編號 $x_i$ 的島嶼,兵力為 $c_i$。
最後接著 $B$ 行,每行兩個正整數 $y_i,d_i$,代表敵國第 $i$ 團軍隊位於編號 $y_i$ 的島嶼,兵力為 $d_i$。
所有同一行的數字將以單一空格隔開。

Output Format

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

Sample Input

Sample Input 1
3 2 1 1 2
1 2
2 3
1 2
3 1

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 Input 3
4 3 1 3 3
1 2
1 3
1 4
1 100
2 8
3 7
4 6

Sample Output

Sample Output 1
2
1 2 2
2 3 2

Sample Output
6
2 3 3
4 3 2
3 5 1
1 2 8
2 3 8
3 5 8

Sample Output 3
3
1 2 8
1 3 7
1 4 6

Hints

測資限制:

  • $2\le N\le 3\times 10^ 5$。
  • $N-1\le M\le \min(\frac{N(N-1)}{2},5\times 10^ 5)$。
  • $1\le A,B\le N$。
  • $2\le A+B\le N$。
  • $N-1\le Q_{upper}\le 3\times 10^ 5$。
  • $1\le u_i,v_i,x_i,y_i \le N$。
  • $u_i\ne v_i$。
  • 沒有連接同樣兩座島嶼的兩座橋樑。
  • $1\le c_i,d_i\le 10^ 9$。
  • $\sum_{i=1}^ A c_i\ge \sum_{i=1}^ B d_i$。
  • 不會有兩團軍隊同時在同一座島嶼。
  • 保證任兩座島嶼都可以經由若干座橋樑互相來往。

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

  1. ($21\%$) $M=N-1$,$u_i=i$,$v_i=i+1$。
  2. ($18\%$) $N\le 500$,$Q_{upper}=3\times 10^ 5$。
  3. ($14\%$) $N\le 500$。
  4. ($23\%$) $A=1$。
  5. ($24\%$) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 3~10 $M=N-1$,$u_i=i$,$v_i=i+1$。 21
2 11~25 $N\le 500$,$Q_{upper}=3\times 10^ 5$。 18
3 11~43 $N\le 500$。 14
4 44~59 $A=1$。 23
5 0~77 無額外限制。 24

Testdata and Limits

No. Time Limit (ms) Memory Limit (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