fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "difference"
  7. #define nl "\n"
  8.  
  9. using ll = long long;
  10.  
  11. inline void rf(){
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.     if (fopen(file ".inp","r")){
  15.         freopen(file ".inp","r",stdin);
  16.         freopen(file ".out","w",stdout);
  17.     }
  18. }
  19.  
  20. struct DSU {
  21.     vector<int> p, sz, mn; // mn: id toàn cục nhỏ nhất trong thành phần
  22.     void init(int n){
  23.         p.resize(n); iota(p.begin(), p.end(), 0);
  24.         sz.assign(n, 1);
  25.         mn.resize(n);
  26.     }
  27.     int f(int x){ return p[x]==x ? x : p[x]=f(p[x]); }
  28.     void un(int a,int b){
  29.         a=f(a); b=f(b);
  30.         if(a==b) return;
  31.         if(sz[a] < sz[b]) swap(a,b);
  32.         p[b]=a; sz[a]+=sz[b]; mn[a]=min(mn[a], mn[b]);
  33.     }
  34. };
  35.  
  36. int main(){
  37.     rf();
  38.  
  39.     int theta;                    // chỉ đọc cho đúng format
  40.     if(!(cin>>theta)) return 0;
  41.  
  42.     int m,n; cin>>m>>n;
  43.     int N = m*n;
  44.  
  45.     vector<ll> a(N);
  46.     for(int i=0;i<m;i++)
  47.         for(int j=0;j<n;j++)
  48.             cin>>a[i*n+j];
  49.  
  50.     auto id = [&](int r,int c){ return r*n + c; };
  51.     auto inb=[&](int r,int c){ return r>=0 && r<m && c>=0 && c<n; };
  52.  
  53.     const int dr[4]={-1,1,0,0};
  54.     const int dc[4]={0,0,-1,1};
  55.  
  56.     struct Edge{ int u,v; ll d; };
  57.     vector<Edge> edges;
  58.     edges.reserve(2LL*N);
  59.  
  60.     for(int r=0;r<m;r++){
  61.         for(int c=0;c<n;c++){
  62.             int u = id(r,c);
  63.             for(int k=0;k<4;k++){
  64.                 int r2=r+dr[k], c2=c+dc[k];
  65.                 if(!inb(r2,c2)) continue;
  66.                 int v = id(r2,c2);
  67.                 if(u < v){
  68.                     edges.push_back({u,v, llabs(a[u]-a[v])});
  69.                 }
  70.             }
  71.         }
  72.     }
  73.  
  74.     sort(edges.begin(), edges.end(),
  75.         [](const Edge& A, const Edge& B){ return A.d < B.d; });
  76.  
  77.     // nén chỉ số đỉnh bằng mảng dùng lại (clear nhanh theo danh sách used)
  78.     vector<int> loc(N, -1);   // id toàn cục -> id cục bộ
  79.     vector<int> used; used.reserve(1<<20);
  80.  
  81.     long long bestK=1; ll bestD=0;
  82.     int bestIdx=0;
  83.  
  84.     for(size_t L=0; L<edges.size(); ){
  85.         size_t R=L; ll d = edges[L].d;
  86.         while(R<edges.size() && edges[R].d==d) R++;
  87.  
  88.         vector<int> nodes; nodes.reserve((R-L)<<1);
  89.         used.clear();
  90.         for(size_t i=L;i<R;i++){
  91.             int u=edges[i].u, v=edges[i].v;
  92.             if(loc[u]==-1){ loc[u]=(int)nodes.size(); nodes.push_back(u); used.push_back(u); }
  93.             if(loc[v]==-1){ loc[v]=(int)nodes.size(); nodes.push_back(v); used.push_back(v); }
  94.         }
  95.  
  96.         DSU dsu; dsu.init((int)nodes.size());
  97.         for(int i=0;i<(int)nodes.size();i++) dsu.mn[i]=nodes[i];
  98.         for(size_t i=L;i<R;i++) dsu.un(loc[edges[i].u], loc[edges[i].v]);
  99.  
  100.         long long curK=1; int curIdx=0;
  101.         for(int i=0;i<(int)nodes.size();i++){
  102.             if(dsu.f(i)==i){
  103.                 long long sz = dsu.sz[i];
  104.                 int mnid = dsu.mn[i];
  105.                 if(sz > curK || (sz==curK && mnid < curIdx)){
  106.                     curK = sz; curIdx = mnid;
  107.                 }
  108.             }
  109.         }
  110.  
  111.         if(curK > bestK ||
  112.            (curK==bestK && d < bestD) ||
  113.            (curK==bestK && d==bestD && curIdx < bestIdx)){
  114.             bestK = curK; bestD = d; bestIdx = curIdx;
  115.         }
  116.  
  117.         for(int u: used) loc[u] = -1; // reset nén cho nhóm này
  118.         L = R;
  119.     }
  120.  
  121.     int x = bestIdx / n + 1;
  122.     int y = bestIdx % n + 1;
  123.     cout << bestK << ' ' << bestD << ' ' << x << ' ' << y << nl;
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
5 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
stdout
copy 
7 1 1 1
https://ideone.com/JgtWWd
language:
C++14 (gcc 8.3)
created:
6 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!