AT_ahc060_a [AHC060A] Ice Cream Collection

国中にアイスクリームの木が生えている Nihonbashi 国では、伝統のバニラと情熱のストロベリーの 2 つの味が至高とされる。 この国ではアイスの量よりも味の組み合わせの多様性が重視されており、いかにアイスを積み重ねるかが日々探求されている。 Nihonbashi 国にはアイスクリームの木とアイスクリームショップがそれぞれ複数存在し、道でつながったグラフ構造を構成している。 あなたはアイスクリーム職人として、このグラフ上を移動しながら、アイスクリームの木でアイスを収穫してコーンの上に積み上げていき、作成したアイスをアイスクリームショップに納品している。 各アイスクリームショップの満足度は、その店に並ぶ在庫の多様性、すなわち何種類の異なる組み合わせのアイスが提供されているかによって決まる。 現在、すべてのアイスクリームショップの在庫は空である。 あなたの使命は、Nihonbashi 国全体のアイスクリームショップの満足度の総和を最大化し、Nihonbashi 国に活気を取り戻すことである。

有一个联通的无向图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $0, 1, \ldots, N-1$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。 每个顶点属于以下两种类型之一： - 冰淇淋店：顶点 $0, 1, \ldots, K-1$（共 $K$ 个顶点）。 - 冰淇淋树：顶点 $K, K+1, \ldots, N-1$（共 $N-K$ 个顶点）。 每个冰淇淋树提供特定口味：香草（`W`，即白色）或草莓（`R`，即红色）。初始时，所有冰淇淋树都提供香草味（`W`）。 你会从顶点 $0$（一家冰淇淋店）出发，手里拿着一支空的甜筒（用一个空字符串表示）。你最多可以进行 $T$ 步操作。每一步，你可以选择以下两种行动之一： - 行动1：从当前位置移动到相邻的顶点 $v$。然后，根据 $v$ 的类型，要么采集冰淇淋，要么交付冰淇淋。 - 如果 $v$ 是冰淇淋树：从该树采集当前口味（`W` 或 `R`），并将其添加到甜筒字符串的末尾。 - 如果 $v$ 是冰淇淋店：将你手中甜筒的当前口味字符串加入该店的库存集合 $S_v$。随后你的甜筒将变为空。你可以送交空字符串，此时空字符串也会被加入到库存集合 $S_v$。 - **限制：你不能返回你上一步刚刚离开的顶点。** 具体来说，如果你上一次行动1是从顶点 $a$ 走到顶点 $b$，那么下一次行动1就不能从 $b$ 再走回 $a$（即使中间进行了行动2）。 - 行动2：仅当你当前位置位于香草味（`W`）的冰淇淋树时才能进行。通过添加草莓汁，该树今后采集出的口味会变为草莓味（`R`）。不能将草莓味的树再变回香草味。 如输入生成部分所述，图是2-边连通的，因此行动1始终可行。 你需要最大化每家冰淇淋店 $v$ 的库存集合 $S_v$ 的大小。请注意，交付已经在 $S_v$ 中存在的字符串不会增加集合的大小。

输入以如下格式从标准输入给出： > $N\; M\; K\; T$ > $A_0\; B_0$ > $\vdots$ > $A_{M-1}\; B_{M-1}$ > $X_0\; Y_0$ > $\vdots$ > $X_{N-1}\; Y_{N-1}$ - 第一行包含四个整数 $N$、$M$、$K$、$T$，分别表示顶点数、边数、冰淇淋店数和最大操作步数。它们满足 $N=100$、$K=10$、$T=10000$。对于 $M$ 的取值，请参考“输入生成”部分。 - 接下来 $M$ 行，每行给出一条边的信息。第 $i$ 条边无向连接顶点 $A_i$ 和 $B_i$。 - 接下来 $N$ 行，每行给出顶点 $i$ 的坐标 $(X_i, Y_i)$，这些坐标在输入生成时用到。$0\leq X_i, Y_i \leq 300$，且任意两个顶点 $i\neq j$，都有 $(X_i, Y_i)\neq (X_j, Y_j)$。如果不需要可跳过读取这些坐标。

输出不超过 $T$ 行，每行格式如下： - 执行动作1时：输出目标顶点的编号 $v$。 > $v$ - 执行动作2时：输出 `-1`。 ``` -1 ```

### 评分方式 你的得分是所有冰淇淋店库存集合 $S_i$ 的大小之和（$0\leq i < K$）：即 $ \sum_{i=0}^{K-1} |S_i| $。 若输出了以下不合法数据，将判为答案错误（WA）： - 在当前位置不是香草味（`W`）的冰淇淋树时执行了行动2。 - 行动1时，指定移动的目标顶点并未与当前位置直接相连。 - 行动1（从第二次起），移动路径回到了上一次行动1的出发顶点。 - 总操作次数超过 $T$。 共150个测试用例。提交代码的总得分为所有测试用例的得分之和。如果你的提交在某些测试用例中输出不合法或超时，则全体提交会被判为WA或TLE，得分为零。比赛期间所得的最高得分将作为最终排名标准，赛后不会有系统测试。同分情况下，参赛者按最后得分并列，不分答题时间。 ### 输入生成 令 $\mathrm{rand}(L,U)$ 表示在区间 $[L,U]$ 内均匀生成一个随机整数。 1. 对每个顶点 $i$，应用 $X_i = \mathrm{rand}(0, 300)$，$Y_i = \mathrm{rand}(0, 300)$。若与已生成的任一顶点欧几里得距离 $\leq 20$ 则重选。重复该过程 $N$ 次完成顶点集 $V$。 2. 计算顶点集 $V$ 的 [Delaunay 三角剖分](https://zh.wikipedia.org/wiki/%E6%96%9C%E6%A0%91#Delaunay%E4%B8%89%E8%A7%92%E5%88%86%E5%89%B2)，其边集记为 $E$。 3. 随机打乱边集 $E$，依次对每条边执行如下操作： - 如果移除此边后，图 $(V, E)$ 仍是2-边连通且无割点，则以概率 $0.7$ 移除此边。 4. 处理完成产生的边集即为最终图的边集。 ### 工具（输入生成与可视化） - [网页版](https://img.atcoder.jp/ahc060/wX0NuJxV.html?lang=zh)：功能较强，支持动画。 - [本地版](https://img.atcoder.jp/ahc060/wX0NuJxV.zip)：需 [Rust编程语言](https://www.rust-lang.org/) 环境。 - [Windows预编译版](https://img.atcoder.jp/ahc060/wX0NuJxV_windows.zip)：若不熟悉Rust环境可用此版本。 请注意：比赛期间禁止分享可视化结果和讨论思路。 由 ChatGPT 5 翻译