SHARE
TWEET

Que 1 Codenation

a guest Jul 15th, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. 3 4
  3. 1 5 7 8
  4. 2 4 1 5
  5. 1 1 1 1
  6. */
  7. /*
  8.  _____ _             _              _           _
  9. |_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  10.   | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  11.   | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  12.   |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|                                                
  13.  
  14. */
  15. #include<bits/stdc++.h>
  16. #define ll          long long
  17. #define pb          push_back
  18. #define ppb         pop_back
  19. #define    endl        '\n'
  20. #define mii         map<ll int,ll int>
  21. #define msi         map<string,ll int>
  22. #define mis         map<ll int, string>
  23. #define rep(i,a,b)    for(ll int i=a;i<b;i++)
  24. #define mpi         map<pair<ll int,ll int>,ll int>
  25. #define pii         pair<ll int,ll int>
  26. #define vi          vector<ll int>
  27. #define vii         vector<pair<ll int, ll int>>
  28. #define vs          vector<string>
  29. #define all(a)      (a).begin(),(a).end()
  30. #define F           first
  31. #define S           second
  32. #define sz(x)       (ll int)x.size()
  33. #define hell        1000000007
  34. #define lbnd        lower_bound
  35. #define ubnd        upper_bound
  36. #define bs          binary_search
  37. #define mp          make_pair
  38. #define what_is(x)  cerr << #x << " is " << x << endl;
  39. #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  40. using namespace std;
  41. #define N  100005
  42. /*
  43. Instructions :
  44.     1. Set p each i of p eqaul to i initailly.
  45.     2. rank is initiialised with 0.
  46.     3. To know parent run a loop for each value call find function.
  47. */
  48. ll ans[N];
  49. ll rank[N];
  50. ll p[N];       // set p of i equal to i initially        
  51. ll find(ll x)
  52. {
  53.     if(p[x]!=x)
  54.         p[x]=find(p[x]);
  55.     return p[x];
  56. }
  57. void merge(ll x,ll y)
  58. {
  59.     ll Px,Py;
  60.     Px=find(x);
  61.     Py=find(y);
  62.     if(::rank[Px]>::rank[Py])
  63.         p[Py]=Px;
  64.     else
  65.         p[Px]=Py;
  66.     if(::rank[Px]==::rank[Py])
  67.         ::rank[Py]++;
  68. }
  69. void solve()
  70. {
  71.     ll n,m;
  72.     cin>>n>>m;
  73.     rep(i,0,n*m+1)
  74.     {
  75.         p[i]=i;
  76.     }
  77.     ll a[n][m];
  78.     rep(i,0,n)
  79.     {
  80.         rep(j,0,m)
  81.         {
  82.             cin>>a[i][j];
  83.         }
  84.     }
  85.     vi row[n],col[m];
  86.     map<ll,vii>pm;
  87.     rep(i,0,n)
  88.     {
  89.         map<ll,ll>tmp;
  90.         rep(j,0,m)
  91.         {
  92.             pm[a[i][j]].pb({i,j});
  93.             if(tmp[a[i][j]])
  94.             {
  95.                 merge(tmp[a[i][j]],i*m+j+1);
  96.             }
  97.             else
  98.             {
  99.                 tmp[a[i][j]]=i*m+j+1;
  100.             }  
  101.         }
  102.     }
  103.     rep(j,0,m)
  104.     {
  105.         map<ll,ll>tmp;
  106.         rep(i,0,n)
  107.         {
  108.             if(tmp[a[i][j]])
  109.             {
  110.                 merge(tmp[a[i][j]],i*m+j+1);
  111.             }
  112.             else
  113.             {
  114.                 tmp[a[i][j]]=i*m+j+1;
  115.             }  
  116.         }
  117.     }
  118.     for(auto i:pm)
  119.     {
  120.         for(auto j:i.S)
  121.         {
  122.             ll par=find(j.F*m+j.S+1);
  123.             if(sz(row[j.F])!=0)
  124.             {
  125.                 ans[par]=max(ans[par],row[j.F].back()+1);
  126.             }
  127.             if(sz(col[j.S])!=0)
  128.             {
  129.                 ans[par]=max(ans[par],col[j.S].back()+1);
  130.             }
  131.         }
  132.         for(auto j:i.S)
  133.         {
  134.             ll par=find(j.F*m+j.S+1);
  135.             row[j.F].pb(ans[par]);
  136.             col[j.S].pb(ans[par]);
  137.         }
  138.     }
  139.     rep(i,0,n)
  140.     {
  141.         rep(j,0,m)
  142.         {
  143.             cout<<ans[find(i*m+j+1)]+1<<" ";
  144.         }
  145.         cout<<endl;
  146.     }
  147.     return;
  148. }
  149. int main()
  150. {
  151.     ios_base::sync_with_stdio(false);
  152.     cin.tie(0);
  153.     cout.tie(0);
  154.     int TESTS=1;
  155.     // cin>>TESTS;
  156.     while(TESTS--)
  157.     {
  158.         solve();
  159.     }
  160.     time
  161.     return 0;
  162. }
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