Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Apr 7th, 2020 166 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool ans[100005];
  4. int t[100005],a[100005],b[100005];
  5. map<pair<int,int>,int> m;
  6. vector<pair<int,int> > tree[400005],u;
  7. vector<int> par[100005],sz[100005];
  8. void update(int node,int st,int en,int l,int r,pair<int,int> e)
  9. {
  10.     if (l<=st && en<=r)
  11.     tree[node].push_back(e);
  12.     if (en<l || st>r || r<l || (l<=st && en<=r))
  13.     return;
  14.     int mid=(st+en)/2;
  15.     update(2*node,st,mid,l,r,e);
  16.     update(2*node+1,mid+1,en,l,r,e);
  17. }
  18. int find(int x)
  19. {
  20.     if (par[x].back()==x)
  21.     return x;
  22.     return find(par[x].back());
  23. }
  24. void Union(int x,int y)
  25. {
  26.     x=find(x);
  27.     y=find(y);
  28.     if (x==y)
  29.     return;
  30.     if (sz[x].back()>sz[y].back())
  31.     swap(x,y);
  32.     par[x].push_back(y);
  33.     sz[y].push_back(sz[x].back()+sz[y].back());
  34.     u.push_back({x,y});
  35. }
  36. void solve(int node,int st,int en)
  37. {
  38.     int curt=u.size();
  39.     for (auto e:tree[node])
  40.     Union(e.first,e.second);
  41.     if (st==en)
  42.     {
  43.         if (t[st]==2)
  44.         ans[st]=(find(a[st])==find(b[st]));
  45.         return;
  46.     }
  47.     int mid=(st+en)/2;
  48.     solve(2*node,st,mid);
  49.     solve(2*node+1,mid+1,en);
  50.     while (u.size()!=curt)
  51.     {
  52.         par[u.back().first].pop_back();
  53.         sz[u.back().second].pop_back();
  54.         u.pop_back();
  55.     }
  56. }
  57. int main()
  58. {
  59.     int n,q;
  60.     cin >> n >> q;
  61.     for (int i=1;i<=n;i++)
  62.     {
  63.         par[i].push_back(i);
  64.         sz[i].push_back(1);
  65.     }
  66.     for (int i=1;i<=q;i++)
  67.     {
  68.         string s;
  69.         cin >> s >> a[i] >> b[i];
  70.         if (a[i]>b[i])
  71.         swap(a[i],b[i]);
  72.         if (s=="add")
  73.         m[{a[i],b[i]}]=i;
  74.         else if (s=="rem")
  75.         {
  76.             t[i]=1;
  77.             update(1,1,q,m[{a[i],b[i]}],i,{a[i],b[i]});
  78.             m[{a[i],b[i]}]=0;
  79.         }
  80.         else
  81.         t[i]=2;
  82.     }
  83.     for (auto p:m)
  84.     {
  85.         if (p.second)
  86.         update(1,1,q,p.second,q,p.first);
  87.     }
  88.     solve(1,1,q);
  89.     for (int i=1;i<=q;i++)
  90.     {
  91.         if (t[i]==2)
  92.         puts(ans[i]? "YES":"NO");
  93.     }
  94. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top