首页 > itarticle > bzoj3673 & 3674

bzoj3673 & 3674

admin 11月 12, 2020 0

为什么 STL 用的这么熟练啊！到底要拿 rope 水过多少道题啊！？你到底要 TLE 多少次你才甘心啊！？

BZOJ 3673 和 3674 完全一样。

代码

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



#include <iostream>
#include <cstdio>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int MAX_V = 2E5 + 1E3;
typedef rope<int> rint;
rint *fa[MAX_V];
int N, M, A[MAX_V];

int Find(int ver, int p) {
    int pfa = fa[ver]->at(p);
    if(pfa == p)
        return p;
    int rt = Find(ver, pfa);
    
    // 路径压缩
    if(rt == pfa)
        return rt;
    fa[ver]->replace(p, rt);
    return rt;
}

void Union(int ver, int x, int y) {
    int Fx = Find(ver, x);
    int Fy = Find(ver, y);
    fa[ver]->replace(Fx, Fy);
}

int lastans = 0;
int main() {
    scanf("%d %d", &N, &M);
    
    for(int i=1;i<=N;i++)
        A[i] = i;
    
    fa[0] = new rint(A, A+N+1);
    int op, a, b;
    for(int i=1;i<=M;i++) {
        fa[i] = new rint(*fa[i-1]);
        scanf("%d", &op);
        switch(op) {
        case 1:
            {
                scanf("%d %d", &a, &b);
                a = a ^ lastans; b = b ^ lastans;
                Union(i, a, b);
            } break;
        case 2:
            {
                scanf("%d", &a);
                a = a ^ lastans;
                fa[i] = fa[a];
            } break;
        case 3:
            {
                scanf("%d %d", &a, &b);
                a = a ^ lastans; b = b ^ lastans;
                printf("%dn", (lastans = (Find(i, a) == Find(i, b))));
            }
        }
    }
}