网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[焦作一中2012]玻璃球游戏
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | marbles.in | 输出文件 | marbles.out |
【问题描述】
小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