| 题目名称 | 1070. [焦作一中2012] 玻璃球游戏 |
|---|---|
| 输入输出 | marbles.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 常庆卫
于2012-09-07加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：86， 提交：337， 通过率：25.52% | ||||
|
Hzoi_chairman |
100 | 0.318 s | 9.47 MiB | C++ |
|
ONCE AGA |
100 | 0.456 s | 7.73 MiB | C++ |
|
Hzoi_chairman |
100 | 0.456 s | 9.47 MiB | C++ |
|
求魔 |
100 | 0.463 s | 5.46 MiB | C++ |
|
骆玉笙 |
100 | 0.466 s | 5.44 MiB | C++ |
|
hanio wi |
100 | 0.470 s | 6.49 MiB | C++ |
|
hanio wi |
100 | 0.471 s | 6.49 MiB | C++ |
|
君见 |
100 | 0.493 s | 8.32 MiB | C++ |
|
ZLJ |
100 | 0.497 s | 6.61 MiB | C++ |
|
刘润达 |
100 | 0.500 s | 4.90 MiB | C++ |
| 本题关联比赛 | |||
| 20120907 | |||
| 2024暑假C班集训8 | |||
| 关于 玻璃球游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
| ||||
|
| ||||
|
回复 @liu_runda :
谢谢 森林
2016-03-10 09:41
9楼
| ||||
|
最后一个点用自己的方法超时http://cojs.tk/cogs/images/bgm/51.gif
 | ||||
|
超时超时超时。。。呵呵
 洛克索耶夫
2016-03-09 17:27
7楼
| ||||
|
先处理完所有删边操作，再逆序处理所有操作（原来的删边处理时改为添边）。
维护一个带权并查集（所谓的权就是会不会走到环路）。 最后一个点用递归find()会爆栈，改迭代find()就可以了。 | ||||
|
| ||||
|
| ||||
【问题描述】
小x的业余生活中，有一项是玩滚玻璃球游戏。
某天，小x想到了一种很无趣的玩法，当然，这种玩法就是为了玩看题的你们。
小x首先建立了一个单向轨道，这个单向轨道可以抽象成一个有向图，每个顶点的出度都是1，也就是由每个点出发，只有一条边连向其他的点。
小x的游戏最初规则是这样的：让玻璃球从某一个点出发，沿着有向边的方向，移动到它的下一个顶点，如果还能移动，就继续移动，直到没有相邻的边，当然会存在在一个环里不停运动的情况。
为了增加难度，小x决定将游戏规则增强，他会提出一系列问题，让你回答：
1） 格式：1 X.查询玻璃球由编号为X的点出发，最终在哪个点停下来，如果能停下来，输出最后的点的编号，如果停不下来，输出”CIKLUS”.
2） 格式：2 X.删除由X出发的那条有向边。
【输入】
第一行包含一个正整数N（1<=N<=300000）,表示图的顶点数。
第二行包含由空格隔开N个正整数，第i个数表示从i顶点可以通过出边到达的定点编号，0表示该点没有出边。
接下来的一行包含1个整数Q（1<=Q<=300000）,表示询问的次数。
再接下来Q行，每行表示一次查询，格式如题目描述。
【输出】
对于第1类询问，输出玻璃球停止时所在顶点编号,每行1个，按照查询的顺序输出。如果玻璃球无法停止，输出”CIKLUS”即可.
【输入输出样例1】
|
marbles.in |
marbles.out |
|
3 2 3 1 7 1 1 1 2 2 1 1 2 1 1 2 2 1 2 |
CIKLUS CIKLUS 1 1 2 |
【输入输出样例2】
|
marbles.in |
marbles.out |
|
5 0 3 5 3 4 6 1 1 1 2 2 4 1 2 2 3 1 2 |
1 CIKLUS 4 3 |
【数据范围】
40% 数据保证 N<=100, Q<=1000
大样例：data