Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(X) (X).begin(), (X).end()
  6. #define pb push_back
  7. #define rall(X) (X).rbegin(), (X).rend()
  8. #define ll long long
  9. #define ull unsigned long long
  10. #define ld long double
  11. #define fir first
  12. #define sec second
  13.  
  14. const int nmax = 2e5;
  15. map<ll, ll> p;
  16. map<ll, set<ll>> mp;
  17.  
  18. void init() {
  19. for (ll i = 0; i < nmax; i++) {
  20. p[i] = i;
  21. }
  22. }
  23.  
  24. ll get(ll a) {
  25. if (p[a] == a)
  26. return a;
  27. else
  28. return p[a] = get(p[a]);
  29. }
  30.  
  31. void unon(ll a, ll b) {
  32. for (auto i: mp[b]) {
  33. mp[a].insert(i);
  34. }
  35. mp[b].clear();
  36. }
  37.  
  38. void unit(ll a, ll b) {
  39. a = get(a);
  40. b = get(b);
  41. if (a < b) {
  42. p[b] = a;
  43. unon(a, b);
  44. } else {
  45. p[a] = b;
  46. unon(b, a);
  47. }
  48. }
  49.  
  50. int main() {
  51. init();
  52. ll n, m; cin >> n >> m;
  53.  
  54. for (ll i = 0; i < m; i++) {
  55. char q; cin >> q;
  56. if (q == '+') {
  57. ll a, b; cin >> a >> b;
  58. unit(a, b);
  59. } else if (q == '-') {
  60. ll a, b; cin >> a >> b;
  61. a = get(a);
  62. b = get(b);
  63. mp[a].insert(b);
  64. mp[b].insert(a);
  65. } else {
  66. ll a, b; cin >> a >> b;
  67. if (get(a) == get(b))
  68. cout << "+\n";
  69. else if (mp[get(a)].find((get(b))) != mp[get(a)].end())
  70. cout << "-\n";
  71. else
  72. cout << "?\n";
  73. }
  74. }
  75. return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement