fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define int long long
  6. #define pb push_back
  7. #define f first
  8. #define s second
  9. #define pq priority_queue
  10. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  11. #define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  12.  
  13. using namespace std;
  14.  
  15. // #include <ext/pb_ds/assoc_container.hpp>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // using namespace __gnu_pbds;
  18.  
  19. // template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. // template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  21.  
  22. vector<pair<int, int>> loc;
  23. vector<vector<int>> ind;
  24. int n, m;
  25.  
  26. struct dsu{
  27.     vector<int> p;
  28.     vector<int> minii, maxii, minij, maxij;
  29.     void build(int n){
  30.         p.assign(n, -1);
  31.         minii.assign(n, 0);
  32.         minij.assign(n, 0);
  33.  
  34.         maxii.assign(n, 0);
  35.         maxij.assign(n, 0);
  36.     }
  37.     int get(int u){
  38.         return (p[u]<0?u:p[u]=get(p[u]));
  39.     }
  40.     void merge(int u, int v){
  41.         if((u=get(u))==(v=get(v))) return;
  42.         if(-p[u]<-p[v]) swap(u, v);
  43.  
  44.         p[u]+=p[v];
  45.  
  46.         minii[u]|=minii[v];
  47.         minij[u]|=minij[v];
  48.  
  49.         maxii[u]|=maxii[v];
  50.         maxij[u]|=maxij[v];
  51.  
  52.         p[v]=u;
  53.     }
  54. };
  55.  
  56. // vector<vector<bool>> vis;
  57. vector<vector<int>> a;
  58.  
  59. dsu d1;
  60.  
  61. int dx[8] = {-1,  1,  0,  0, -1, -1,  1,  1};
  62. int dy[8] = { 0,  0, -1,  1, -1,  1, -1,  1};
  63.  
  64. bool valid(int i, int j){
  65.     return (i>=0&&i<n&&j>=0&&j<m);
  66. }
  67.  
  68. void solve(){
  69.     cin>>n>>m;
  70.     a.assign(n, vector<int>(m));
  71.     loc.assign(n*m+10, {-1, -1});
  72.     ind.assign(n, vector<int>(m));
  73.     d1.build(n*m+10);
  74.     for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin>>a[i][j];
  75.  
  76.     int cntr=0;
  77.     for(int i=0; i<n; i++){
  78.         for(int j=0; j<m; j++){
  79.             loc[cntr]={i, j};
  80.             ind[i][j]=cntr;
  81.             cntr++;
  82.         }
  83.     }
  84.  
  85.     for(int i=0; i<n; i++){
  86.         for(int j=0; j<m; j++){
  87.             if(i==0){
  88.                 d1.minii[ind[i][j]]=true;
  89.             }
  90.             if(j==0){
  91.                 d1.minij[ind[i][j]]=true;
  92.             }
  93.             if(i==n-1){
  94.                 d1.maxii[ind[i][j]]=true;
  95.             }
  96.             if(j==m-1){
  97.                 d1.maxij[ind[i][j]]=true;
  98.             }
  99.         }
  100.     }
  101.  
  102.     for(int i=0; i<n; i++){
  103.         for(int j=0; j<m; j++){
  104.             for(int k=0; k<8; k++){
  105.                 if(valid(i+dy[k], j+dx[k])&&a[i+dy[k]][j+dx[k]]==a[i][j]){
  106.                     d1.merge(ind[i][j], ind[i+dy[k]][j+dx[k]]);
  107.                 }
  108.             }
  109.         }
  110.     }
  111.  
  112.     for(int i=0; i<n; i++){
  113.         map<int, int> m1;
  114.         for(int j=0; j<m; j++){
  115.             if(m1.count(a[i][j])) {
  116.                 d1.merge(ind[i][j], m1[a[i][j]]);
  117.             }
  118.  
  119.             m1[a[i][j]]=ind[i][j];
  120.         }
  121.     }
  122.     for(int j=0; j<m; j++){
  123.         map<int, int> m1;
  124.         for(int i=0; i<n; i++){
  125.             if(m1.count(a[i][j])) {
  126.                 d1.merge(ind[i][j], m1[a[i][j]]);
  127.             }
  128.             m1[a[i][j]]=ind[i][j];
  129.         }
  130.     }
  131.  
  132.     vector<int> v1;
  133.     for(int i=0; i<n; i++){
  134.         for(int j=0; j<m; j++){
  135.             int vertix=d1.get(ind[i][j]);
  136.             if(d1.minij[vertix]&&d1.maxij[vertix]){ // left right
  137.                 v1.pb(a[i][j]);
  138.             }
  139.             if(d1.minij[vertix]&&d1.minii[vertix]){ // left top
  140.                 v1.pb(a[i][j]);
  141.             }
  142.             if(d1.maxii[vertix]&&d1.minii[vertix]){ // down top
  143.                 v1.pb(a[i][j]);
  144.             }
  145.             if(d1.maxii[vertix]&&d1.maxij[vertix]){ // down right
  146.                 v1.pb(a[i][j]);
  147.             }
  148.         }
  149.     }
  150.  
  151.     sort(v1.begin(), v1.end());
  152.  
  153.     int mex=0;
  154.     for(int i=0; i<v1.size(); i++){
  155.         if(v1[i]==mex) mex++;
  156.     }
  157.     cout<<mex<<endl;
  158. }
  159.  
  160. int32_t main() {
  161.     fast;
  162.  
  163.     int t;
  164.     t=1;
  165.     cin>>t;
  166.     while(t--){
  167.         solve();
  168.     }
  169.     return 0;
  170. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/c4yAx2
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!