【HDOJ】1512 Monkey King

左偏树+并查集。左偏树就是可合并二叉堆。

/* 1512 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000")

#define sti                set<int>
#define stpii            set<pair<int, int> >
#define mpii            map<int,int>
#define vi                vector<int>
#define pii                pair<int,int>
#define vpii            vector<pair<int,int> >
#define rep(i, a, n)     for (int i=a;i<n;++i)
#define per(i, a, n)     for (int i=n-1;i>=a;--i)
#define clr                clear
#define pb                 push_back
#define mp                 make_pair
#define fir                first
#define sec                second
#define all(x)             (x).begin(),(x).end()
#define SZ(x)             ((int)(x).size())
#define lson            l, mid, rt<<1
#define rson            mid+1, r, rt<<1|1

typedef struct node_t {
    int l, r, f, v, dis;
    
    node_t() {}
    
    node_t(int l_, int r_, int f_, int v_):
        l(l_), r(r_), f(f_), v(v_) {}
    
} node_t;

const int maxn = 1e5+5;
node_t H[maxn];

int find(int x) {
    if (H[x].f == x)
        return x;
    return H[x].f = find(H[x].f);
}

int merge(int a, int b) {
    if (a == 0)    return b;
    if (b == 0)    return a;
    
    if (H[a].v < H[b].v)    swap(a, b);
    H[a].r = merge(H[a].r, b);
    H[H[a].r].f = a;
    if (H[H[a].l].dis < H[H[a].r].dis)    swap(H[a].l, H[a].r);
    H[a].dis = H[H[a].r].dis + 1;
    
    return a;
}

int pop(int a) {
    int l = H[a].l, r = H[a].r;
    
    H[l].f = l;
    H[r].f = r;
    
    H[a].l = H[a].r = H[a].dis = 0;
    return merge(l, r);
}

int main() {
    ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
        freopen("data.out", "w", stdout);
    #endif
    
    int n, m;
    int x, y;
    int fx, fy;
    int ans;
    
    H[0].dis = -1;
    H[0].l = H[0].r = H[0].f = H[0].v = 0;
    while (scanf("%d", &n) != EOF) {
        rep(i, 1, n+1) {
            scanf("%d", &H[i].v);
            H[i].l = H[i].r = H[i].dis = 0;
            H[i].f = i;
        }
        
        scanf("%d", &m);
        while (m--) {
            scanf("%d %d", &x, &y);
            fx = find(x);
            fy = find(y);
            
            if (fx == fy) {
                puts("-1");
            } else {
                H[fx].v >>= 1;
                x = pop(fx);
                x = merge(x, fx);
                
                H[fy].v >>= 1;
                y = pop(fy);
                y = merge(y, fy);
                
                x = merge(x, y);
                ans = H[x].v;
                printf("%d\n", ans);
            }
        }
    }
    
    #ifndef ONLINE_JUDGE
        printf("time = %d.\n", (int)clock());
    #endif
    
    return 0;
}

 然后用优先级队列+并查集试了一下居然也过了，左偏树是764ms，而优先级队列是811ms。

/* 1512 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000")

#define sti                set<int>
#define stpii            set<pair<int, int> >
#define mpii            map<int,int>
#define vi                vector<int>
#define pii                pair<int,int>
#define vpii            vector<pair<int,int> >
#define rep(i, a, n)     for (int i=a;i<n;++i)
#define per(i, a, n)     for (int i=n-1;i>=a;--i)
#define clr                clear
#define pb                 push_back
#define mp                 make_pair
#define fir                first
#define sec                second
#define all(x)             (x).begin(),(x).end()
#define SZ(x)             ((int)(x).size())
#define lson            l, mid, rt<<1
#define rson            mid+1, r, rt<<1|1

const int maxn = 1e5+5;
int pre[maxn];
priority_queue<int, vi, less<int> > Q[maxn];

int find(int x) {
    if (x == pre[x])
        return x;
    return pre[x] = find(pre[x]);
}

int main() {
    ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
        freopen("data.out", "w", stdout);
    #endif
    
    int n, m;
    int x, y, fx, fy;
    int ma, mb;
    int ans, tmp;
    
    while (scanf("%d", &n)!=EOF) {
        rep(i, 1, n+1) {
            scanf("%d", &tmp);
            while (!Q[i].empty())
                Q[i].pop();
            Q[i].push(tmp);
            pre[i] = i;
        }
        
        scanf("%d", &m);
        while (m--) {
            scanf("%d %d", &x, &y);
            fx = find(x);
            fy = find(y);
            
            if (fx == fy) {
                puts("-1");
            } else {
                ma = Q[fx].top();
                Q[fx].pop();
                Q[fx].push(ma>>1);
                
                mb = Q[fy].top();
                Q[fy].pop();
                Q[fy].push(mb>>1);
                
                if (SZ(Q[fx]) > SZ(Q[fy]))
                    swap(fx, fy);
                    
                pre[fx] = fy;
                while (!Q[fx].empty()) {
                    Q[fy].push(Q[fx].top());
                    Q[fx].pop();
                }
                
                ans = Q[fy].top();
                printf("%d\n", ans);
            }
        }
    }
    
    #ifndef ONLINE_JUDGE
        printf("time = %d.\n", (int)clock());
    #endif
    
    return 0;
}