Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define eb emplace_back
  5. #define pb push_back
  6. #define pii pair<int,int>
  7. #define fi first
  8. #define se second
  9. #define all(x) x.begin(),x.end()
  10. #pragma GCC optimize("O3")
  11. #pragma GCC optimize("unroll-loops")
  12. #pragma GCC target("avx2")
  13.  
  14. using namespace std;
  15.  
  16. vector<int> p;
  17. vector<int> sz;
  18. vector< set<int> > s;
  19.  
  20. int get_par(int v){
  21. if(p[v]==v) return v;
  22. p[v] = get_par(p[v]);
  23. return p[v];
  24. }
  25.  
  26. void unite(int a, int b){
  27. a = get_par(a);
  28. b = get_par(b);
  29. if(a==b) return;
  30. if(sz[a]<sz[b]) swap(a,b);
  31. //a is par
  32. sz[a]+=sz[b];
  33. p[b] = a;
  34. if(s[a].size()<s[b].size()){
  35. swap(s[a],s[b]);
  36. }
  37. for(auto t:s[b]){
  38. s[a].insert(get_par(t));
  39. }
  40. }
  41.  
  42. main(){
  43. ios::sync_with_stdio(false);
  44. cin.tie(0);
  45. int n,k;
  46. cin>>n>>k;
  47. sz.resize(n,1);
  48. s.resize(n,set<int>());
  49. p.resize(n);
  50. for(int i = 0; i < n; i++) p[i] = i;
  51.  
  52. for(int i = 0; i < k; i++){
  53. char c;
  54. int a,b;
  55. cin>>c>>a>>b;
  56. a--;b--;
  57. if(c=='+') unite(a,b);
  58. else if(c=='-'){
  59. a = get_par(a);
  60. b = get_par(b);
  61. s[b].insert(a);
  62. s[a].insert(b);
  63. }else{
  64. a = get_par(a);
  65. b = get_par(b);
  66. if(a==b){
  67. cout<<"+\n";
  68. }else if(s[a].find(b)!=s[a].end() || s[b].find(a)!=s[b].end()){
  69. cout<<"-\n";
  70. }else{
  71. cout<<"?\n";
  72. }
  73. }
  74. }
  75.  
  76.  
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement