#include <bits/stdc++.h>
using namespace std;
class UFDS {
typedef vector<int> vi;
public:
vi p, rak, setSize;
int numSets;
void create(int n){
setSize.assign(n, 1);
numSets = n;
rak.assign(n, 0);
p.assign(n, 0);
for(int i =0;i < n;i++){
p[i] = i;
}
}
void reset(){
for(int i = 0;i < p.size();i++){
p[i] = i;
rak[i] = 0;
setSize[i] = 0;
}
numSets = p.size();
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
void unionSet(int i, int j){
if(isSameSet(i,j))
return;
numSets--;
int x = findSet(i);
int y = findSet(j);
if(rak[x] > rak[y]) {
p[y] = x; setSize[x] += setSize[y];
}
else {
p[x] = y; setSize[y] += setSize[x];
if(rak[x] == rak[y]) rak[y]++;
}
}
};
int n, m;
inline int t(int i, int j){
return i * (m+1) + j;
}
inline int diff(multiset<long long> s){
if(s.empty()) return 0;
long long l = *s.begin();
long long r = *(--s.end());
return r - l;
}
int main(){
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int arr[n][m];
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
cin >> arr[i][j];
long long low = -1;
long long high = 1023456789ll;
UFDS uf;
uf.create((n+1)*(m+1)+5);
while(true){
if(low == high - 1) break;
long long s = (low + high) / 2;
uf.reset();
for(int i = 0;i < n;i++){
multiset<long long> a;
multiset<long long> b;
for(int j = 0;j < m;j++){
a.insert(arr[i][j]);
}
if(diff(a) <= s){
for(int j = 0;j <= m;j++){
uf.unionSet(t(i,j),t(i+1,j));
}
}
else{
for(int j = 0;j < m-1;j++){
b.insert(arr[i][j]);
a.erase(a.find(arr[i][j]));
if(diff(a) <= s && diff(b) <= s){
uf.unionSet(t(i,j+1),t(i+1,j+1));
}
}
}
}
for(int j = 0;j < m;j++){
multiset<long long> a;
multiset<long long> b;
for(int i = 0;i < n;i++){
a.insert(arr[i][j]);
}
if(diff(a) <= s){
for(int i = 0;i <= n;i++){
uf.unionSet(t(i,j),t(i,j+1));
}
}
else{
for(int i = 0;i < n-1;i++){
b.insert(arr[i][j]);
a.erase(a.find(arr[i][j]));
if(diff(a) <= s && diff(b) <= s){
uf.unionSet(t(i+1,j),t(i+1,j+1));
}
}
}
}
if(uf.isSameSet(t(0,0),t(n,m)) || uf.isSameSet(t(0,m),t(n,0))){
high = s;
}
else{
low = s;
}
}
cout << high << "\n";
}
Compilation message
joioi.cpp: In member function 'void UFDS::reset()':
joioi.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < p.size();i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
