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
#include <bits/stdc++.h>
using namespace std;

int n,q;
int status[300003]; //-1:has, 0:doesn't have, other:belongs to a group where almost everyone has

int groupIndex = 0;
unordered_map<int, unordered_set<int>> grp;

void removeGroup(int grpInd) {
    for(auto nr: grp.find(grpInd)->second) {
        status[nr] = -1;
    }
    grp.erase(grpInd);
}

void joinGroups(int grp1, int grp2) {
    if(grp.find(grp1)->second.size() < grp.find(grp2)->second.size()) {
        int tmp = grp1;
        grp1 = grp2;
        grp2 = tmp;
    }
    auto it = grp.find(grp1); // bigger group
    for(auto nr: grp.find(grp2)->second) {
        status[nr] = grp1;
        it->second.insert(nr);
    }
    grp.erase(grp2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i=0;i<q;i++) {
        char op;
        int nr1;
        cin >> op >> nr1;
        if(op == '+') {
            int nr2;
            cin >> nr2;
            int g1 = status[nr1];
            int g2 = status[nr2];
            if(nr1==nr2) {
                if(g1 > 0) {
                    removeGroup(g1);
                } else if(g1 == 0) {
                    status[nr1] = -1;
                } else {
                    cout << "incorrect data1";
                    return 0;
                }
            } else if(g1 > 0) {
                if(g2 > 0) {
                    if(g1 == g2) {
                        removeGroup(g1);
                    } else {
                        joinGroups(g1, g2);
                    }
                } else if(g2 == 0) {
                    grp.find(g1)->second.insert(nr2);
                    status[nr2] = g1;
                } else if(g2 == -1) {
                    removeGroup(g1);
                }
            } else if(g1 == 0) {
                if(g2 > 0) {
                    grp.find(g2)->second.insert(nr1);
                    status[nr1] = g2;
                } else if(g2 == 0) {
                    // create common group
                    groupIndex++;
                    status[nr1] = groupIndex;
                    status[nr2] = groupIndex;
                    unordered_set<int> s;
                    s.insert(nr1);
                    s.insert(nr2);
                    grp[groupIndex] = s;
                } else if(g2 == -1) {
                    status[nr1] = -1;
                }
            } else if(g1 == -1) {
                if(g2 > 0) {
                    removeGroup(g2);
                } else if(g2 == 0) {
                    status[nr2] = -1;
                } else if(g2 == -1) {
                    cout << "incorrect data2";
                    return 0;
                }
            }
        } else if(op == '?') {
            int g = status[nr1];
            if(g == -1) cout << '1';
            else if(g == 0) cout << '0';
            else cout << '?';
        } else if(op == '-') {
            int g = status[nr1];
            if(g > 0) {
                auto it = grp.find(g);
                it->second.erase(nr1);
                if(it->second.size()==1) {
                    status[*(it->second.begin())] = 0;
                    grp.erase(g);
                }
            }
            status[nr1] = 0;
        }

        /*cout << endl << "grp ---------------- ";
        for(auto p: grp) {
            cout << p.first << ": ";
            for(auto nr: p.second) {
                cout << nr << ",";
            }
            cout << endl;
        }
        for(int i=1;i<=n;i++) {
            cout << status[i];
        }
        cout << endl;*/
    }
    return 0;
}