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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//
// Created by piotr on 11.03.2024.
//
#include <cassert>
#include <cstdio>
#include <list>
#include <unordered_set>
#include <vector>

class Sets {
    using set_of_ints = std::unordered_set<int>;
    using list_of_sets = std::list<set_of_ints>;

    const int N;
    list_of_sets list; // na początku pusty zbiór jako sentinel
    std::vector<list_of_sets::iterator> pointers;

public:
    Sets(int N) : N(N) {
        list.emplace_back();
        pointers.resize(N, list.begin());
    }

    const set_of_ints* find(int n) const {
        if (pointers[n] == list.begin()) {
            return nullptr; // nie ma go nigdzie
        }
        return &*pointers[n];
    }

    void merge(int n, int m) {
        if (pointers[n] == list.begin() && pointers[m] == list.begin()) {
            // tworzymy nowy zbiór {n,m}
            auto iterator = list.insert(list.end(), set_of_ints());
            iterator->insert(n);
            iterator->insert(m);
            pointers[n] = iterator;
            pointers[m] = iterator;
            return;
        }

        if (pointers[n] != list.begin() && pointers[m] != list.begin()) {
            // łączymy dwa rozłączne zbiory
            auto itn = pointers[n], itm = pointers[m];
            assert(itn != itm);
            if (itn->size() < itm->size()) {
                std::swap(itn, itm);
            }
            for (int x : *itm) {
                pointers[x] = itn;
            }
            itn->merge(*itm);
            list.erase(itm);
            return;
        }

        if (pointers[n] == list.begin() && pointers[m] != list.begin()) {
            std::swap(n, m);
        }
        if (pointers[n] != list.begin() && pointers[m] == list.begin()) {
            // dołączamy m do zbioru n
            pointers[m] = pointers[n];
            pointers[m]->insert(m);
        }
    }

    void deleteSet(int n) {
        auto iterator = pointers[n];
        assert(iterator != list.begin());

        for (int m : *iterator) {
            pointers[m] = list.begin();
        }
        list.erase(iterator);
    }

    void deleteFromSet(int n) {
        auto iterator = pointers[n];
        assert(iterator != list.begin());

        iterator->erase(n);
        pointers[n] = list.begin();
    }
};

int main() {
    int N, Q;
    assert(scanf("%d %d\n", &N, &Q) == 2);

    Sets sets(N);
    std::vector<char> state(N, '0');

    while (Q-- > 0) {
        const char c = getchar();

        if (c == '?') {
            int a;
            assert(scanf("%d\n", &a) == 1); --a;
            putchar(state[a]);

        } else if (c == '-') {
            int a;
            assert(scanf("%d\n", &a) == 1); --a;
            // zakładamy, że state był '1'
            auto set_a = sets.find(a);
            if (set_a) {
                if (set_a->size() > 2) {
                    sets.deleteFromSet(a);
                }
                else {
                    for (int n: *set_a) {
                        state[n] = '0';
                    }
                    sets.deleteSet(a);
                }
            }
            state[a] = '0';

        } else if (c == '+') {
            int a, b;
            assert(scanf("%d %d\n", &a, &b) == 2); --a, --b;
            if (state[a] == '1') {
                a = b;
            } else if (state[b] == '1') {
                b = a;
            }

            if (a == b) {
                // zakładamy, że state był '0'
                // to znaczy, że wszyscy pozostali mają komputery
                // i ma go też a
                auto set_a = sets.find(a);
                if (set_a) {
                    for (int n : *set_a) {
                        state[n] = '1';
                    }
                    sets.deleteSet(a);
                }
                state[a] = '1';

            } else {
                auto set_a = sets.find(a);
                auto set_b = sets.find(b);
                if (set_a && set_b && set_a == set_b) {
                    // teraz wszyscy z danego zbioru mają komputery
                    for (int n : *set_a) {
                        state[n] = '1';
                    }
                    sets.deleteSet(a);
                } else {
                    sets.merge(a, b);
                    state[a] = '?';
                    state[b] = '?';
                }
            }

        }
    }
    putchar('\n');
}