TIOJ 1783：養殖手觸

TIOJ 1783：養殖手觸

題目大意：有 $n$ 個觸手，分為 $A$ 類與 $B$ 類，有四種操作，第 $0$ 種會有 $x$ 與 $y$，代表 $x,y$ 是同一類的觸手；第 $1$ 種會有 $x$ 與 $y$，代表 $x,y$ 是不同類的觸手；第 $2$ 種會有 $x$，代表 $x$ 變成與原本相反的觸手；第 $3$ 種會有 $x$，代表 $x$ 的種類變為未知。一開始都不知道觸手是哪一種，只能通過這些操作來判斷，但是可能會有一些操作與前面的操作矛盾，要求出矛盾的操作量。

解法：我一開始原本直接把小的集合併到大的集合，結果直接 $\text{MLE}$，後來發現可以用並查集，$to_i$ 代表這個節點指向哪個節點，$opp_i$ 代表與 $to_i$ 相反種類的節點，每次合併時要一些特判，然後有可能會需要新增新的節點，但最後很不幸的 $\text{SF}$ 了，我才發現一開始不能將 $to_i$ 設為 $i$，要指向額外的節點才行。在過程中我又寫了另一個比較不複雜的解法，就是假設 $x$ 為 $A$ 類觸手成立，它會跟哪些人在一起，假設 $x$ 為 $B$ 類觸手成立，它又會跟哪些人在一起。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e6 + 5;

int cnt, to[3 * SIZE], opp[3 * SIZE];

int dsu (int x) {return x == to[x] ? x : (to[x] = dsu (to[x]));}

void Merge (int a, int b) {
    int oa = opp[a], ob = opp[b];
    to[b] = a;
    if (oa && ob) {
        to[ob] = oa;
    } else if (ob) {
        opp[a] = ob;
        opp[ob] = a;
    }
}

void Diff (int a, int b) {
    int oa = opp[a], ob = opp[b];
    if (oa) {
        Merge (b, oa);
    } else if (ob) {
        Merge (a, ob);
    } else {
        opp[a] = b;
        opp[b] = a;
    }
}

void Change (int a) {
    int ga = dsu (a), oa = opp[ga];
    cnt++, to[cnt] = to[a] = cnt;
    Diff (cnt, ga);
}

int n, q, ans;

void solve() {
    cin >> n >> q;
    cnt = n;
    FOR (i, 1, n) cnt++, to[i] = to[cnt] = cnt;
    while (q--) {
        int ty, a, b, ga, gb;
        cin >> ty;
        if (ty == 0) {
            cin >> a >> b;
            ga = dsu (a), gb = dsu (b);
            if (opp[ga] == gb) {
                ans++;
                continue;
            }
            Merge (ga, gb);
        } else if (ty == 1) {
            cin >> a >> b;
            ga = dsu (a), gb = dsu (b);
            if (ga == gb) {
                ans++;
                continue;
            }
            Diff (ga, gb);
        } else if (ty == 2) {
            cin >> a;
            Change (a);
        } else {
            cin >> a;
            cnt++, to[cnt] = to[a] = cnt;
        }
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e6 + 5;

int n, q, ans;
int cnt, to[6 * SIZE];

int dsu (int x) {return to[x] == x ? x : (to[x] = dsu (to[x]));}

void Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a != b) {
        to[b] = a;
    }
}

void solve() {
    cin >> n >> q;
    cnt = 2 * n;
    FOR (i, 1, 2 * n) cnt++, to[i] = to[cnt] = cnt;
    while (q--) {
        int ty, a, b;
        cin >> ty >> a;
        if (ty == 0) {
            cin >> b;
            if (dsu (a) == dsu (n + b)) {
                ans++;
                continue;
            }
            Merge (a, b);
            Merge (n + a, n + b);
        } else if (ty == 1) {
            cin >> b;
            if (dsu (a) == dsu (b)) {
                ans++;
                continue;
            }
            Merge (a, n + b);
            Merge (b, n + a);
        } else if (ty == 2) {
            int ori = dsu (a), iro = dsu (n + a);
            cnt++, to[a] = to[cnt] = cnt;
            Merge (iro, cnt);
            cnt++, to[n + a] = to[cnt] = cnt;
            Merge (ori, cnt);
        } else {
            cnt++, to[a] = to[cnt] = cnt;
            cnt++, to[n + a] = to[cnt] = cnt;
        }
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！