Submission #161412

#	Time	Username	Problem	Language	Result	Execution time	Memory
161412		oolimry	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	4 ms	376 KiB

joioi

#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 (stderr)

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++){
                 ~~^~~~~~~~~~

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