网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
爱争吵的猴子
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | monkeyk.in | 输出文件 | monkeyk.out |
【问题描述】
在一个森林里,住着N只好斗的猴子.开始,他们各自为政,互不相干.但是猴子们不能消除争吵,但这仅仅发生在两只互不认识的猴子之间.当争吵发生时,争吵的两只猴子都会求助他们各自最强壮的朋友,并且决斗.当然,决斗之后,两只猴子及他们所有的朋友都相互认识了,并且成为朋友,争吵将不会在他们之间发生.
假定每一只猴子有一个强壮值,在每次决斗之后变为原来的一半(例如,10将为变为5,5将会变为2).
假定每一只猴子认识他自己. 也就是当他发生争吵,并且自己是他的朋友中最强壮的,他将代表自己进行决斗.
【输入格式】
有几组测试数据,每组测试数据由两部分构成.
第一部分:第一行有一个整数 N(N<=100,000),表示猴子的数量.下面有N行.每行有一个数,表示猴子的强壮值(<=32768).
第二部分:第一行有一个整数M(M<=100,000),表示有M次争吵发生.下面有M行,每行有两个整数x和y,表示在第x只猴子和第y只猴子之间发生争吵.
【输出格式】
对于每一次争吵,如果两只猴子认识,输出-1,否则输出一个数,表示决斗后朋友中最强壮猴子的强壮值.
【输入输出样例】
monkeyk.in
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
monkeyk.out
8
5
5
-1
10
5
5
-1
10