Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.34 KB | None | 0 0
  1. /*#pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")*/
  5. #include <iostream>
  6. #include <complex>
  7. #include <vector>
  8. #include <string>
  9. #include <algorithm>
  10. #include <cstdio>
  11. #include <numeric>
  12. #include <cstring>
  13. #include <ctime>
  14. #include <cstdlib>
  15. #include <set>
  16. #include <map>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <list>
  20. #include <cmath>
  21. #include <bitset>
  22. #include <cassert>
  23. #include <queue>
  24. #include <stack>
  25. #include <deque>
  26. #include <random>
  27.  
  28. using namespace std;
  29.  
  30. #define pb push_back
  31. #define all(x) x.begin(), x.end()
  32. #define rall(x) x.rbegin(), x.rend()
  33. #define Str(x) to_string(x)
  34. #define len(s) (int)s.size()
  35.  
  36. typedef long long ll;
  37. typedef long double lld;
  38. typedef string str;
  39. typedef unsigned long long ull;
  40.  
  41. const int maxn = 1e5 + 228;
  42.  
  43. int dsu[maxn], sz[maxn];
  44. vector <int> t[maxn];
  45. map <int, bool> g[maxn];
  46.  
  47. int get(int v) {
  48. return v == dsu[v] ? v : dsu[v] = get(dsu[v]);
  49. }
  50.  
  51. void Merge(int a, int b) {
  52. a = get(a);
  53. b = get(b);
  54. if (a == b)
  55. return;
  56. if (sz[a] < sz[b])
  57. swap(a, b);
  58. sz[a] += sz[b];
  59. sz[b] = 0;
  60. for (auto it : g[b]) {
  61. int x = get(it.first);
  62. g[x][a] = true;
  63. g[a][x] = true;
  64. }
  65. dsu[b] = a;
  66. }
  67.  
  68. void add(int a, int b) {
  69. a = get(a);
  70. b = get(b);
  71. if (a == b)
  72. assert(0);
  73. g[a][b] = 1;
  74. g[b][a] = 1;
  75. }
  76.  
  77. void call(int a, int b) {
  78. a = get(a);
  79. b = get(b);
  80. if (a == b) {
  81. cout << "+\n";
  82. return;
  83. }
  84. if (g[a].count(b)) {
  85. cout << "-\n";
  86. } else {
  87. cout << "?\n";
  88. }
  89. }
  90.  
  91. int main() {
  92. ios_base::sync_with_stdio(false);
  93. cin.tie(NULL);
  94. cout.tie(NULL);
  95. #ifdef LOCAL
  96. freopen("input.txt", "r", stdin);
  97. freopen("output.txt", "w", stdout);
  98. #endif
  99. for (int i = 0; i < maxn; i++) {
  100. dsu[i] = i;
  101. sz[i] = 1;
  102. }
  103. int n, k;
  104. cin >> n >> k;
  105. for (int i = 0; i < k; i++) {
  106. char c;
  107. int x, y;
  108. cin >> c >> x >> y;
  109. if (c == '+') {
  110. Merge(x, y);
  111. } else if (c == '-'){
  112. add(x, y);
  113. } else {
  114. call(x, y);
  115. }
  116. }
  117.  
  118.  
  119. return 0;
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement