Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, k, s[100001], p[100001], a, b;
  6. char h;
  7. set <pair <int, int>> r;
  8.  
  9. int f(int x)
  10. {
  11. int g = x;
  12. while (p[g] != g)
  13. g = p[g];
  14. return g;
  15. }
  16.  
  17. int main()
  18. {
  19. iostream::sync_with_stdio(0); cin.tie(0);
  20. cin >> n >> k;
  21. for (int i = 1 ; i <= n ; i++)
  22. {
  23. s[i] = 1;
  24. p[i] = i;
  25. }
  26. for (int xx = 0 ; xx < k ; xx++)
  27. {
  28. cin >> h >> a >> b;
  29. if (h == '+')
  30. {
  31. a = f(a);
  32. b = f(b);
  33. if (a != b)
  34. {
  35. if (s[a] < s[b])
  36. swap(a, b);
  37. s[a] += s[b];
  38. p[b] = a;
  39. }
  40. }
  41. else if (h == '-')
  42. {
  43. a = f(a);
  44. b = f(b);
  45. r.insert({a, b});
  46. }
  47. else
  48. {
  49. a = f(a);
  50. b = f(b);
  51. if (a == b)
  52. {
  53. cout << "+\n";
  54. continue;
  55. }
  56. if (a > b)
  57. swap(a, b);
  58. set <pair <int, int>> t;
  59. for (pair <int, int> g: r)
  60. {
  61. int i, j;
  62. tie(i, j) = g;
  63. i = f(i);
  64. j = f(j);
  65. if (i > j)
  66. swap(i, j);
  67. t.insert({i, j});
  68. }
  69. r.clear();
  70. int er = 0;
  71. for (pair <int, int> g: t)
  72. {
  73. r.insert(g);
  74. if (a == g.first && b == g.second)
  75. er++;
  76. }
  77. if (er)
  78. cout << "-\n";
  79. else
  80. cout << "?\n";
  81. }
  82. }
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement