oj.uz

답안 #53684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53684 2018-07-01T02:32:43 Z KieranHorgan The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 470 ms 63464 KB 
#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((grid[i+1][j  ]==-1)||
       (grid[i-1][j  ]==-1)||
       (grid[i  ][j+1]==-1)||
       (grid[i  ][j-1]==-1)) {
      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;
//    for(int i = 1; i <= n; i++)
//      for(int j = 1; j <= m; j++)
//        cerr << grid[i][j] << " \n"[j==m];
//    cerr << aMax-aMin << " " << *rem.rbegin()-*rem.begin() << endl;
//    cerr << endl;
    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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 63352 KB Output is correct
2 Incorrect 470 ms 63464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 63352 KB Output is correct
2 Incorrect 470 ms 63464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 63352 KB Output is correct
2 Incorrect 470 ms 63464 KB Output isn't correct
3 Halted 0 ms 0 KB -