Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#pragma GCC optimize ("-O3,unroll-loops")
- #define forn(n) for(int i = 0; i < n; i++)
- #define rforn(n) for (int i = n-1; i>= 0; i--)
- #define forni(n) for(int i = 0; i < n; i++)
- #define fornj(n) for(int j = 0; j < n; j++)
- #define foruv(u, v) for (int i = u; i < v; i++)
- #define F first
- #define S second
- #define X first
- #define Y second
- #define PB push_back
- #define INS insert
- #define ER erase
- #define MP make_pair
- //optimizers
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize("no-stack-protector")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- //#pragma GCC optimize("fast-math")
- using namespace std;
- template<typename T> inline ostream & operator<< (ostream &_out, vector<T> &_v) { for (auto &_i : _v) { _out << _i << " "; } return _out; }
- template<typename T> inline istream & operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
- template<typename T1, typename T2> inline ostream & operator<< (ostream &_out, pair<T1, T2> &_p) { { _out << _p.first << " " << _p.second; } return _out; }
- template<typename T1, typename T2> inline istream & operator>> (istream &_in, pair<T1, T2> &_p) { { _in >> _p.first >> _p.second; } return _in; }
- template <typename T1, typename T2> bool setmin(T1& a, T2 b) { if (b < a) { a = b; return 1; } return 0; }
- template <typename T1, typename T2> bool setmax(T1& a, T2 b) { if (b > a) { a = b; return 1; } return 0; }
- template <typename T> void incvec(vector<T> &v) {for_each(v.begin(), v.end(), [](T &x){x++;});}
- mt19937 rnd(42);
- typedef long long ll;
- typedef unsigned int ui;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<vector<int> > vvi;
- typedef vector<vector<ll> > vvll;
- vector<int> parent;
- set<int> ne[100001];
- int find(int v) {
- if (parent[v] == -1 || v == parent[v])
- return v;
- int x = parent[v];
- while (parent[x] != -1 && parent[x] != x)
- x = parent[x];
- parent[v] = x;
- return x;
- }
- void unite(int a, int b) {
- if (ne[a].size() > ne[b].size())
- swap(a, b);
- for (int i : ne[find(a)]) {
- ne[find(b)].insert(find(i));
- ne[find(i)].insert(find(b));
- }
- parent[find(a)] = find(b);
- }
- signed main() {
- int n, k, op, a, b;
- cin >> n >> k;
- parent.resize(n + 1, -1);
- for (int i = 0; i < k; ++i) {
- cin >> op >> a >> b;
- if (op == '+') {
- unite(a, b);
- } else if (op == '-') {
- ne[find(a)].insert(find(b));
- ne[find(b)].insert(find(a));
- } else if (op == '?') {
- if (find(a) == find(b)) cout << "+" << endl;
- else if (ne[find(a)].find(find(b)) != ne[find(a)].end())
- cout << "-" << endl;
- else cout << "?" << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement