JacobianDet

Untitled

Apr 2nd, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define mp std::make_pair
  4.  
  5. typedef long long ll;
  6.  
  7. std::pair<int, int> E[100001];
  8. bool ecut[100001];
  9. int arr[100001], rank[100001];
  10. std::vector<std::pair<int, bool> > res;
  11.  
  12. bool cmpx(std::pair<int, bool> A, std::pair<int, bool> B)
  13. {
  14.     return (A.first < B.first);
  15. }
  16.  
  17. struct qry
  18. {
  19.     int id, ty, a1, a2;
  20.     ll tx;
  21.  
  22.     bool operator < (const qry& wx) const
  23.     {
  24.         return (tx > wx.tx);
  25.     }
  26. };
  27.  
  28. std::set<qry> MX;
  29.  
  30. class dsu
  31. {
  32.     public: int root(int x);
  33.             void find_union(int x, int y);
  34. };
  35.  
  36. int dsu::root(int x)
  37. {
  38.     return (x == arr[x]) ? x : (arr[x] = root(arr[x]));
  39. }
  40.  
  41. void dsu::find_union(int x, int y)
  42. {
  43.     int rx = root(x);
  44.     int ry = root(y);
  45.     if(rx == ry)
  46.     return;
  47.     if(rank[ry] > rank[rx])
  48.     {
  49.         int tmp = ry;
  50.         ry = rx;
  51.         rx = tmp;
  52.     }  
  53.     arr[ry] = rx;
  54.     if(rank[rx] == rank[ry])
  55.     rank[rx]++;
  56.     return;
  57. }
  58.  
  59. int main(void)
  60. {
  61.     std::ios_base::sync_with_stdio(false);
  62.     std::cin.tie(NULL);
  63.     std::cout.tie(NULL);
  64.     int n;
  65.     std::cin>>n;
  66.     for(int i=0;i<n-1;i++)
  67.     {
  68.         int s,d;
  69.         std::cin>>s>>d;
  70.         E[i] = mp(s, d);
  71.     }  
  72.     dsu T;
  73.     for(int i=1;i<=n;i++)
  74.     {
  75.         arr[i] = i;
  76.         rank[i] = 0;
  77.     }
  78.     int q;
  79.     std::cin>>q;
  80.     for(int i=0;i<q;i++)
  81.     {
  82.         int ty, a1, a2 = -1;
  83.         ll tx;
  84.         std::cin>>ty>>tx>>a1;
  85.         if(ty == 2)
  86.         std::cin>>a2;
  87.         else
  88.         {
  89.             a1--;
  90.             ecut[a1] = 1;
  91.         }  
  92.         MX.insert({i, ty, a1, a2, tx});
  93.     }  
  94.     for(int i=0;i<n-1;i++)
  95.     {
  96.         if(!ecut[i])
  97.         T.find_union(E[i].first, E[i].second); 
  98.     }
  99.     for(auto u : MX)
  100.     {  
  101.         if(u.ty == 1)
  102.         T.find_union(E[u.a1].first, E[u.a1].second);
  103.         else
  104.         {
  105.             if(T.root(u.a1) == T.root(u.a2))
  106.             res.pb(mp(u.id, 1));
  107.             else res.pb(mp(u.id, 0));
  108.         }  
  109.     }
  110.     std::sort(res.begin(), res.end(), cmpx);
  111.     for(auto u : res)
  112.     std::cout<<u.second<<"\n";
  113.     return 0;  
  114. }
Add Comment
Please, Sign In to add comment