Submission #53683

#	Time	Username	Problem	Language	Result	Execution time	Memory
53683		KieranHorgan	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	222 ms	63484 KiB

joioi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 998244353;

int grid[2005][2005];
int vis[2005][2005];
int proces[2005][2005];

int dfs(int i, int j) {
  vis[i][j] = 1;
  int x = 1;
  if(grid[i+1][j  ] != -1 && vis[i+1][j  ]==0) x += dfs(i+1, j  );
  if(grid[i-1][j  ] != -1 && vis[i-1][j  ]==0) x += dfs(i-1, j  );
  if(grid[i  ][j+1] != -1 && vis[i  ][j+1]==0) x += dfs(i  , j+1);
  if(grid[i  ][j-1] != -1 && vis[i  ][j-1]==0) x += dfs(i  , j-1);
  return x;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  int n, m;
  cin >> n >> m;

  multiset<int> rem;

  memset(grid, -1, sizeof(grid));
  int mi=1,mj=1;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> grid[i][j];
      if(grid[i][j] > grid[mi][mj])
        mi=i,mj=j;
      rem.insert(grid[i][j]);
    }
  }

  int aMax = grid[mi][mj];
  int aMin = grid[mi][mj];

  int ans = 1ll<<40;
  priority_queue<pair<int, pair<int, int>>> pq;
  pq.push({grid[mi][mj], {mi, mj}});
  proces[mi][mj] = 1;
  while(!pq.empty()) {
    int i = pq.top().second.first;
    int j = pq.top().second.second;
    grid[i][j] = pq.top().first;
    int storeGrid = grid[i][j];
    pq.pop();
    if((int)(grid[i+1][j  ]==-1)+
       (int)(grid[i-1][j  ]==-1)+
       (int)(grid[i  ][j+1]==-1)+
       (int)(grid[i  ][j-1]==-1) >= 2) {
      grid[i][j] = -1;
      int x = 0;
      memset(vis, 0, sizeof(vis));
      if(grid[i+1][j  ]!=-1) x=dfs(i+1, j  );
      else if(grid[i-1][j  ]!=-1) x=dfs(i-1, j  );
      else if(grid[i  ][j+1]!=-1) x=dfs(i  , j+1);
      else if(grid[i  ][j-1]!=-1) x=dfs(i  , j-1);
      grid[i][j] = storeGrid;
      if(x+1 != rem.size()) {
        proces[i][j]=0;
        continue;
      }
    }
    aMin = min(aMin, storeGrid);
    rem.erase(rem.find(storeGrid));
    if(rem.empty()) break;

    ans = min(ans, max(aMax-aMin, *rem.rbegin()-*rem.begin()));
    grid[i][j] = -1;
    if(grid[i-1][j  ]!=-1 && proces[i-1][j  ]==0) {pq.push({grid[i-1][j  ], {i-1, j  }}); proces[i-1][j  ]=1; };
    if(grid[i+1][j  ]!=-1 && proces[i+1][j  ]==0) {pq.push({grid[i+1][j  ], {i+1, j  }}); proces[i+1][j  ]=1; };
    if(grid[i  ][j-1]!=-1 && proces[i  ][j-1]==0) {pq.push({grid[i  ][j-1], {i  , j-1}}); proces[i  ][j-1]=1; };
    if(grid[i  ][j+1]!=-1 && proces[i  ][j+1]==0) {pq.push({grid[i  ][j+1], {i  , j+1}}); proces[i  ][j+1]=1; };
  }
  cout << ans << endl;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(x+1 != rem.size()) {
          ~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40