at3107

Untitled

Sep 28th, 2020 (edited)
901
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int N=100005;
  2. int parent[N],ma[N],siz[N];
  3. #define ll long long
  4. int find(int v)
  5. {
  6.     if(v==parent[v]) return v;
  7.     return parent[v]=find(parent[v]);
  8. }
  9. void uni(int a,int b)
  10. {
  11.     if(siz[a]<siz[b]) swap(a,b);
  12.     siz[a]+=siz[b];
  13.     parent[b]=a;
  14.     ma[a]=max(a,b);
  15.     ma[b]=ma[a];
  16.     return ;
  17. }
  18. vector<int> fun(int n,vector<int> v1,vector<int> v2)
  19. {
  20.     ll last=((n)*(n+1))/2;
  21.     for(int i=1;i<=n;i++)
  22.     {
  23.         parent[i]=i;
  24.         siz[i]=1;
  25.         ma[i]=i;
  26.     }
  27.     vector<int> ans;
  28.     int m=v1.size();
  29.     for(int i=0;i<m;i++)
  30.     {
  31.         int a=find(v1[i]),b=find(v2[i]);
  32.         if(a!=b)
  33.         {
  34.             last-=ma[a];
  35.             last-=ma[b];
  36.             uni(a,b);
  37.             last+=ma[find(a)];
  38.         }
  39.         ans.push_back(last);
  40.     }
  41.     return ans;
  42. }
RAW Paste Data