Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#pragma GCC optimize ("-O3,unroll-loops")
  3. #define forn(n) for(int i = 0; i < n; i++)
  4. #define rforn(n) for (int i = n-1; i>= 0; i--)
  5. #define forni(n) for(int i = 0; i < n; i++)
  6. #define fornj(n) for(int j = 0; j < n; j++)
  7. #define foruv(u, v) for (int i = u; i < v; i++)
  8. #define F first
  9. #define S second
  10. #define X first
  11. #define Y second
  12. #define PB push_back
  13. #define INS insert
  14. #define ER erase
  15. #define MP make_pair
  16. //optimizers
  17. //#pragma GCC optimize("Ofast")
  18. //#pragma GCC optimize("no-stack-protector")
  19. //#pragma GCC optimize("unroll-loops")
  20. //#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  21. //#pragma GCC optimize("fast-math")
  22. using namespace std;
  23.  
  24. template<typename T> inline ostream & operator<< (ostream &_out, vector<T> &_v) { for (auto &_i : _v) { _out << _i << " "; } return _out; }
  25. template<typename T> inline istream & operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
  26. template<typename T1, typename T2> inline ostream & operator<< (ostream &_out, pair<T1, T2> &_p) { { _out << _p.first << " " << _p.second; } return _out; }
  27. template<typename T1, typename T2> inline istream & operator>> (istream &_in, pair<T1, T2> &_p) { { _in >> _p.first >> _p.second; } return _in; }
  28. template <typename T1, typename T2> bool setmin(T1& a, T2 b) { if (b < a) { a = b; return 1; } return 0; }
  29. template <typename T1, typename T2> bool setmax(T1& a, T2 b) { if (b > a) { a = b; return 1; } return 0; }
  30. template <typename T> void incvec(vector<T> &v) {for_each(v.begin(), v.end(), [](T &x){x++;});}
  31. mt19937 rnd(42);
  32.  
  33. typedef long long ll;
  34. typedef unsigned int ui;
  35. typedef long double ld;
  36. typedef pair<int, int> pi;
  37. typedef pair<ll, ll> pll;
  38. typedef vector<int> vi;
  39. typedef vector<ll> vl;
  40. typedef vector<vector<int> > vvi;
  41. typedef vector<vector<ll> > vvll;
  42.  
  43. vector<int> parent;
  44. set<int> ne[100001];
  45.  
  46. int find(int v) {
  47. if (parent[v] == -1 || v == parent[v])
  48. return v;
  49. int x = parent[v];
  50. while (parent[x] != -1 && parent[x] != x)
  51. x = parent[x];
  52. parent[v] = x;
  53. return x;
  54. }
  55.  
  56. void unite(int a, int b) {
  57. if (ne[a].size() > ne[b].size())
  58. swap(a, b);
  59. for (int i : ne[find(a)]) {
  60. ne[find(b)].insert(find(i));
  61. ne[find(i)].insert(find(b));
  62. }
  63. parent[find(a)] = find(b);
  64. }
  65.  
  66. signed main() {
  67. int n, k, op, a, b;
  68. cin >> n >> k;
  69. parent.resize(n + 1, -1);
  70. for (int i = 0; i < k; ++i) {
  71. cin >> op >> a >> b;
  72. if (op == '+') {
  73. unite(a, b);
  74. } else if (op == '-') {
  75. ne[find(a)].insert(find(b));
  76. ne[find(b)].insert(find(a));
  77. } else if (op == '?') {
  78. if (find(a) == find(b)) cout << "+" << endl;
  79. else if (ne[find(a)].find(find(b)) != ne[find(a)].end())
  80. cout << "-" << endl;
  81. else cout << "?" << endl;
  82. }
  83. }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement