QOJ.ac

QOJ

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif

#17169. 木制棋子

Statistiques

这是一个交互式问题。

Vlad 有一个包含 $n$ 个顶点的空有向图,顶点编号为 $1$ 到 $n$。他计划逐一向该图中添加 $n - 1$ 条有向边,并确保在任何时刻都满足以下两个条件:

  1. 该图是一个有向森林:每个连通分量都是一棵有向有根树的形式,其中边的方向是从根节点指向叶子节点。
  2. 对于图中的每个顶点,从该顶点可达的顶点集合是一个连续的整数区间(即中间没有空隙)。

你的任务是在每次添加边后检查这两个条件是否满足。

交互协议

首先,评测程序将提供一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$),表示顶点数。

接下来,将进行 $n - 1$ 次加边操作。对于每次操作,评测程序将输入两个顶点编号 $v$ 和 $u$ ($1 \le v, u \le n; v \ne u$)。请检查在添加有向边 $v \to u$ 后是否满足 Vlad 的条件,并在单独的一行中按以下格式输出答案:

  • 如果不满足第一个条件,输出字符串 "Bad oriented forest"
  • 如果不满足第二个条件,输出字符串 "Bad segment at v",其中 $v$ 是任意一个不满足该条件的顶点编号。
  • 如果两个条件都不满足,输出上述两条消息中的任意一条。
  • 否则,如果两个条件都满足,输出字符串 "Good"

如果任何一个条件不满足,你的程序在输出相应的消息后应立即终止,即使处理的边数少于 $n - 1$ 条。

不会重复添加相同的有向边 $v \to u$。所有 $n - 1$ 次加边操作都是预先确定的。

样例

输入样例 1

6
1 2
3 4
3 1
5 6
5 1

输出样例 1

Good
Good
Good
Good
Bad segment at 5

说明

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jiangly2026-03-06 01:31:13View

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.