#include <bits/stdc++.h>
using namespace std;
bool connects(int Y, int X, vector<vector<int>> copy, int H, int W){
queue<pair<int, int>> que;
que.push({X, Y});
while(!que.empty()){
int x = que.front().first, y = que.front().second;
que.pop();
if(!copy[x][y]){
continue;
}
copy[x][y] = 0;
if(x > 0){
que.push({x-1, y});
}
if(y > 0){
que.push({x, y-1});
}
if(x < H-1){
que.push({x+1, y});
}
if(y < W-1){
que.push({x, y+1});
}
}
int ok = 0;
for(auto i :copy){
for(int j : i){
ok |= j;
}
}
//cout << "AFTER CHECK" << endl;
// for(int i = 0; i < H; i ++){
// for(int j = 0; j < W; j ++){
// cout << copy[i][j] << " ";
// }
//cout << endl;
//}
//cout << endl << endl;
if(!ok){
return true;
}
return false;
}
int main(){
int H, W;
cin >> H >> W;
set<vector<int>> in, out;
vector<vector<int>> grid(H, vector<int>(W));
int minx, miny, mini = 1e9, maxx, maxy, maxi = 0;
for(int i = 0; i < H; i ++){
for(int j = 0; j < W; j ++){
cin >> grid[i][j];
if(maxi < grid[i][j]){
maxi = grid[i][j];
maxy = j;
maxx = i;
}
if(mini > grid[i][j]){
mini = grid[i][j];
miny = j;
minx = i;
}
}
}
int L = 0, R = 1000000000;
while(L < R){
int mid = (L + R) / 2;
vector<vector<int>> copy = grid;
int max_can = mini + mid, max_got = 0, min_left = 1e9;
queue<pair<int, int>> que;
que.push({minx, miny});
while(!que.empty()){
int x = que.front().first, y = que.front().second;
que.pop();
if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){
continue;
}
copy[x][y] = 0;
bool can = connects(maxy, maxx, copy, H, W);
//cout << can << endl;
if(!can){
copy[x][y] = grid[x][y];
continue;
}
else{
if(x > 0){
que.push({x-1, y});
}
if(y > 0){
que.push({x, y-1});
}
if(x < H-1){
que.push({x+1, y});
}
if(y < W-1){
que.push({x, y+1});
}
}
}
int min_untaken = 1e9;
for(int i = 0; i < H; i ++){
for(int j = 0; j < W; j ++){
//cout << copy[i][j] << " ";
if(copy[i][j])
min_untaken = min(min_untaken, grid[i][j]);
}
//cout << endl;
}
int delta = max(mid, maxi - min_untaken);
//cout << mid << " " << delta << endl;
if(delta > mid){
L = mid + 1;
}
else{
R = mid;
}
}
cout << L << endl;
return 0;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:70:35: warning: unused variable 'max_got' [-Wunused-variable]
70 | int max_can = mini + mid, max_got = 0, min_left = 1e9;
| ^~~~~~~
joioi.cpp:70:48: warning: unused variable 'min_left' [-Wunused-variable]
70 | int max_can = mini + mid, max_got = 0, min_left = 1e9;
| ^~~~~~~~
joioi.cpp:76:49: warning: 'maxy' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){
| ~~~~~~~~~^~~~~~~~~~~~~
joioi.cpp:76:37: warning: 'maxx' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
