fork download 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define fi first
  4. #define se second
  5. using namespace std;
  6. const int N=505;
  7. const int MN=2.5e5+5;
  8. const int dx[]={1,-1,0,0};
  9. const int dy[]={0,0,1,-1};
  10. int n,m,q,a[N][N],l[MN],r[MN],ans[MN],p[MN];
  11. pii qr[MN],pos[MN];
  12.  
  13. int get(int u){
  14.     return(u==p[u]?u:p[u]=get(p[u]));
  15. }
  16. void join(int u,int v){
  17.     u=get(u);v=get(v);
  18.     p[v]=u;
  19. }
  20. int main()
  21. {
  22.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  23.     freopen("shutdown.inp","r",stdin);
  24.     freopen("shutdown.out","w",stdout);
  25.     cin>>n>>m>>q;
  26.     for(int i=1;i<=n;i++){
  27.         for(int j=1;j<=m;j++)cin>>a[i][j],pos[a[i][j]]={i,j};
  28.     }
  29.     for(int i=1;i<=q;i++){
  30.         cin>>qr[i].fi>>qr[i].se;
  31.         ans[i]=min(qr[i].fi,qr[i].se);
  32.         l[i]=1;r[i]=ans[i]-1;
  33.     }
  34.     while(1){
  35.         vector<vector<int>>g(n*m+1);
  36.         bool ok=1;
  37.         for(int i=1;i<=q;i++){
  38.             if(l[i]<=r[i]){
  39.                 ok=0;
  40.                 g[(l[i]+r[i])>>1].push_back(i);
  41.             }
  42.         }
  43.         if(ok)break;
  44.         for(int i=1;i<=m*n;i++)p[i]=i;
  45.         for(int i=m*n;i>=1;i--){
  46.             for(int j:g[i]){
  47.                 //cout<<i<<' '<<j<<' '<<get(qr[j].fi)<<' '<<get(qr[j].se)<<'\n';
  48.                 if(get(qr[j].fi)!=get(qr[j].se)){
  49.                     ans[j]=i;
  50.                     r[j]=i-1;
  51.                 }
  52.                 else l[j]=i+1;
  53.             }
  54.             int u=pos[i].fi;
  55.             int v=pos[i].se;
  56.             for(int k=0;k<4;k++){
  57.                 int x=u+dx[k];
  58.                 int y=v+dy[k];
  59.                 if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]>i)join(a[x][y],i);
  60.             }
  61.         }
  62.     }
  63.     for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
4 4 2
15 16 1 9
14 13 4 8
6 5 3 7
12 11 2 10
14 10
15 11
stdout 
Standard output is empty
https://ideone.com/KEOwdE
language:
C++14 (gcc 8.3)
created:
10 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!