QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB Total points: 100

# 4985. 打怪游戏

Statistics

Time Limit: 3s → 6s

你正在玩一个打怪的小游戏。游戏在一张地图上进行,你的任务是手持武器,消灭地图上的所有怪物。

地图上有 $n$ 座城市,$m$ 条无向道路相连这些城市,使得所有的城市都能通过道路直接或间接相连。每个城市上有一个怪物,第 $i$ 座城市的怪物血量是 $a_i$ 。

最初,你有 $k$ 把武器,第 $i$ 把武器的耐久值为 $b_i$ 。

你可以任选一个城市出发,沿道路行进。每当你第一次到达某个城市时,你需要与那里的怪物作战。作战规则为:你按照编号顺序使用手里的第一把武器,如果武器当前的耐久不低于怪物的血量,你就可以打死怪物,但武器会减少相当于怪物血量的耐久值;如果当前的武器耐久低于怪物血量,你便不能用这把武器打怪,需要立刻将这把武器丢弃并换下一把;如果你没有武器可换了,你就输掉了游戏。

同时,地图上有 $q$ 个道具,分布在不同的城市,第 $i$ 个道具位于城市 $c_i$,其属性值为 $d_i$。每当你打死一个城市的怪物之后,如果这个城市有道具,你获得之。道具的作用是当你打怪的时候,你可以事先对怪使用一个道具使得怪的血量减少 $d_i$,减少到 $0$ 为止。每个道具最多只能被使用一次,每个怪只能被使用至多一个道具,注意道具并不需要获得后立刻使用。

请问:你能否战胜所有的怪?如果能,请求出最优策略(即使用的武器数量 $x$ 最少,如有并列则最后一把使用的武器的剩余耐久 $y$ 最高),并输出 $x$ 和 $y$;如果不能取胜,只需输出一个字符串 FAIL

输入格式

第 $1$ 行,$4$ 个非负整数 $n,m,k,q$。

接下来 $m$ 行,每行 $2$ 个正整数 $u_i,v_i$,表示一条连接城市 $u_i$ 与 $v_i$ 的道路。

接下来 $1$ 行, $n$ 个正整数 $a_i$,表示怪物的血量。

接下来 $1$ 行,$k$ 个正整数 $b_i$,表示武器的初始耐久值。

接下来 $q$ 行,每行 $2$ 个正整数 $c_i,d_i$,描述一个道具。

输出格式

输出共一行,如果存在获胜策略,输出 $2$ 个正整数 $x,y$,表示最优策略下使用了前 $x$ 把武器,最后一把使用的武器的剩余耐久是 $y$;如果不能取胜,输出一个字符串 FAIL

样例数据

样例 1 输入

3 2 2 2
1 2
2 3
2 3 5
2 6
2 2
3 3

样例 1 输出

2 1

样例 1 解释

你的最优策略是先打城市 $3$ 的怪物。虽然你会直接丢弃武器 $1$,但你接下来可以凭借道具在不消耗耐久的前提下战胜城市 $2$ 和城市 $1$ 的怪物。如果选择先打城市 $1$ 的怪物,最后武器 $2$ 将只剩 $0$ 点耐久。

样例 2 输入

3 3 3 2
1 2
2 3
1 3
3 3 5
3 3 3
1 1
2 1

样例 2 输出

FAIL

样例 2 解释

因为你不能把两个道具都对城市 $3$ 的怪物使用,因此你无论如何也打不赢它。

子任务

对于全部数据,$1\leq n \leq 18$,$n-1\leq m \leq n(n-1)/2$,$1\leq k \leq n$,$0\leq q \leq min(n,8)$,$1 \leq a_i,b_i \leq 10^9$,$1 \leq c_i \leq n$,$1 \leq d_i \leq 10^9$,$1 \leq u_i,v_i \leq n$,$u_i \neq v_i$。保证所有 $c_i$ 互不相同,保证任何一对城市之间最多只有一条道路直接相连,且保证给出的图联通。

子任务编号 分值 $n \leq$ $q \leq$ 特殊性质
$1$ $5$ $5$ $5$
$2$ $12$ $8$ $8$
$3$ $7$ $12$ $0$
$4$ $13$ $8$
$5$ $8$ $18$ $0$
$6$ $9$ $8$ $k=1$
$7$ $11$ $b_i \leq 10$
$8$ $14$ $m=n(n-1)/2$
$9$ $21$