#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);
int sz = (n+1)*(m+1);
while(true){
if(low == high - 1) break;
long long s = (low + high) / 2;
//cout << s << "\n";
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));
//cout << t(i,j) << " " << t(i+1,j) << "\n";
//adj[t(i,j)].push_back(t(i+1,j));
//adj[t(i+1,j)].push_back(t(i,j));
}
}
else{
for(int j = 0;j < m;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));
//cout << t(i,j+1) << " " << t(i+1,j+1) << "\n";
//adj[t(i,j)].push_back(t(i+1,j));
//adj[t(i+1,j)].push_back(t(i,j));
}
}
}
}
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));
//cout << t(i,j) << " " << t(i,j+1) << "\n";
//adj[t(i,j)].push_back(t(i,j+1));
//adj[t(i,j+1)].push_back(t(i,j));
}
//if(s == 7) return 0;
}
else{
for(int i = 0;i < n;i++){
b.insert(arr[i][j]);
a.erase(a.find(arr[i][j]));
if(diff(a) <= s && diff(b) <= s){
//cout << t(i+1,j) << " " << t(i+1,j+1) << "\n";
uf.unionSet(t(i+1,j),t(i+1,j+1));
//adj[t(i+1,j)].push_back(t(i+1,j+1));
//adj[t(i+1,j+1)].push_back(t(i+1,j));
}
}
//if(s == 15) return 0;
}
}
/*
queue<int> bfs;
bfs.push(t(0,0));
while(!bfs.empty()){
int u = bfs.front();
bfs.pop();
if(vis[u]) continue;
vis[u] = true;
for(int v : adj[u]){
bfs.push(v);
}
}
if(vis[t(n,m)]){
high = s;
continue;
}
fill(vis,vis+sz,false);
bfs.push(t(n,0));
while(!bfs.empty()){
int u = bfs.front();
bfs.pop();
if(vis[u]) continue;
vis[u] = true;
for(int v : adj[u]){
bfs.push(v);
}
}
if(vis[t(0,m)]){
high = s;
}
else{
low = s;
}
*/
if(uf.isSameSet(t(0,0),t(n,m)) || uf.isSameSet(t(0,m),t(n,0))){
high = s;
//cout << "yes\n";
}
else{
low = s;
}
//if(s < 20) break;
//break;
}
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++){
~~^~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:83:6: warning: unused variable 'sz' [-Wunused-variable]
int sz = (n+1)*(m+1);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
544 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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
544 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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
544 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
