Skip to content

12107: 【原2107】体育节之战

题目

题目描述

author: Diao Kelu 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2107

Description

这次体育节多了一个新项目,神还没有确定它的名字,不过他在人间的代言人已经知道了一些关于这个项目的内容:

\(n\)个人,每个人有个强度值\(a_i\)(编号从1开始),最开始的时候大家都不认识。然后有\(m\)次冲突发生,每次冲突发生在2个不认识的人之间(如果两个人本来就认识,则不发生冲突),这时双方各自会找自己所认识的人中最强的人出来决斗,经过决斗之后他们就互相认识了(并且他们原本认识的人现在都互相认识了)。决斗后,决斗双方的强度值会减半(向下取整)。

神想知道对于每次决斗,参与决斗的人所认识的所有人中最大的强度值(决斗后)。希望你能写一个程序帮他解决这个问题。

Input Format

输入共有\(n + m + 2\)行。

第\(1\)行有\(1\)个整数\(n\),表示参与这个项目的人数

第\(2\)到\(n + 1\)行每行有\(1\)个整数,分别表示每个人的强度值。

第\(n + 2\)行是一个整数\(m\)。

第\(n + 3\)到\(m + n + 2\)行描述\(m\)组询问,即冲突双方的编号

Output Format

输出\(m\)行,每行是对于询问的回答(参与决斗的人所认识的所有人中最大的强度值)。

如果询问的两个人本来就认识,那么输出-1

注意:输出决斗以后的组里强度值最大的,不是两位参加决斗者强度值。

Sample Input

5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5

Sample Output

8
5
5
-1
10

About Test Data

对于30%的数据,\(1 \leq m, n \leq 1000\)。

对于70%的数据,\(1 \leq n \leq 100000, 1 \leq m \leq 1000\)。

对于100%的数据,\(1 \leq n \leq 100000, 1 \leq m \leq 100000\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!