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
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

struct Data {
    unordered_set<int> citizens;
    char type;
};

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<Data *> arr;
    arr.resize(n + 1, nullptr);
    for (int i = 0; i < q; ++i) {
        char c;
        cin >> c;
        switch (c) {
        case '+': {
            int a, b;
            cin >> a >> b;
            if (arr[a] != nullptr && arr[b] != nullptr) {
                if (arr[a] == arr[b]) {
                    arr[a]->type = 'c';
                } else {
                    Data *bigger = arr[a]->citizens.size() > arr[b]->citizens.size() ? arr[a] : arr[b];
                    Data *smaller = bigger == arr[a] ? arr[b] : arr[a];
                    bigger->type = arr[a]->type == 'c' || arr[b]->type == 'c' ? 'c' : 't';
                    for (int citizen : smaller->citizens) {
                        arr[citizen] = bigger;
                    }
                    bigger->citizens.insert(begin(smaller->citizens), end(smaller->citizens));
                    delete smaller;
                }
            } else if (arr[a] != nullptr) {
                arr[b] = arr[a];
                arr[b]->citizens.insert(b);
            } else if (arr[b] != nullptr) {
                arr[a] = arr[b];
                arr[a]->citizens.insert(a);
            } else {
                arr[a] = new Data{};
                arr[b] = arr[a];
                arr[a]->citizens.insert(a);
                arr[b]->citizens.insert(b);
                arr[a]->type = a == b ? 'c' : 't';
            }
            break;
        }
        case '-': {
            int c;
            cin >> c;
            if (arr[c]->citizens.size() == 1) {
                delete arr[c];
                arr[c] = nullptr;
            } else if (arr[c]->citizens.size() == 2) {
                if (arr[c]->type == 'c') {
                    arr[c]->citizens.erase(c);
                    arr[c] = nullptr;
                } else {
                    auto ptr = arr[c];
                    arr[*ptr->citizens.begin()] = nullptr;
                    arr[*++ptr->citizens.begin()] = nullptr;
                    delete ptr;
                }
            } else {
                arr[c]->citizens.erase(c);
                arr[c] = nullptr;
            }
            break;
        }
        case '?': {
            int d;
            cin >> d;
            if (!arr[d]) {
                cout << '0';
            } else if (arr[d]->type == 'c') {
                cout << '1';
            } else {
                cout << '?';
            }
            break;
        }
        }
    }
    cout << endl;
}