Submission #161407

#	Time	Username	Problem	Language	Result	Execution time	Memory
161407		oolimry	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	4 ms	504 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);
	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 (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++){
                 ~~^~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:83:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz = (n+1)*(m+1);
      ^~
joioi.cpp:68:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("i.txt","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~

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