Monkey King
Problem Description
Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted. Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2). And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.
Input
There are several test cases, and each case consists of two parts. First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768). Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.
Output
For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.
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
Author
JIANG, Yanyan
Source
题目类型：并查集+可并堆(斜堆)
算法分析：先将每个节点看成是一个堆，然后使用并查集来查询当前输入的两个节点的父节点，如果两个节点的父节点相同，则表明两个猴子在一个群体中，直接输出-1，否则使用斜堆将每个堆的堆顶元素的值更新(先删除堆顶元素，然后再插入一个值为原来堆顶元素一半的元素)。最后将两个堆合并成一个堆并返回堆顶元素即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 66; struct node { int key, lson, rson; }; node tr[maxn]; int par[maxn]; void Init () { memset (tr, 0, sizeof (tr)); for (int i = 0; i < maxn; i++) par[i] = i; } int Merge (int a, int b) { if (!a) return b; if (!b) return a; if (tr[a].key < tr[b].key) swap (a, b); tr[a].rson = Merge (tr[a].rson, b); par[tr[a].rson] = a; swap (tr[a].rson, tr[a].lson); return a; } int Del (int a) { int lch = tr[a].lson, rch = tr[a].rson; par[lch] = lch, par[rch] = rch; tr[a].lson = tr[a].rson = 0; return Merge (lch, rch); } int UnFind (int val) { if (par[val] == val) return val; return par[val] = UnFind (par[val]); } int main() { // CPPFF; int n; while (cin >> n) { Init (); for (int i = 1; i <= n; i++) cin >> tr[i].key; int q; cin >>q; for (int i = 1; i <= q; i++) { int u, v; cin >> u >> v; u = UnFind (u); v = UnFind (v); if(u == v) cout << "-1" << endl; else { int ta = Del (u); int tb = Del (v); tr[u].key /= 2; tr[v].key /= 2; ta = Merge (u, ta); tb = Merge (v, tb); int tt = Merge (ta, tb); cout << tr[tt].key << endl; } } } return 0; } |