Submission #1132327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132327		henriess	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	320 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;


vector<vector<long long>> grid;
vector<pair<long long,long long>> moves = {{0,-1},{0,1},{-1,0},{1,0}};

long long h,w;

multiset<long long> ogvals;

bool is_valid_split(const vector<vector<bool>>& vis) {
    // Check row connectivity
    for (int i = 0; i < h; ++i) {
        bool in_region = false;
        for (int j = 0; j < w; ++j) {
            if (vis[i][j]) {
                if (!in_region) in_region = true;
            } else {
                if (in_region) return false; // Non-contiguous JOI region in row
            }
        }
    }

    // Check column connectivity
    for (int j = 0; j < w; ++j) {
        bool in_region = false;
        for (int i = 0; i < h; ++i) {
            if (vis[i][j]) {
                if (!in_region) in_region = true;
            } else {
                if (in_region) return false; // Non-contiguous JOI region in column
            }
        }
    }

    return true;
}


long long bfs(long long mid){
	multiset<long long> vals = ogvals;
	queue<pair<pair<long long,long long>,pair<long long,long long>>> nodes;

	long long first = grid[0][0];
	long long iteration = 0;
	nodes.push({{0,0},{first,iteration}});
	vals.erase(first);
	
	vector<vector<bool>> vis;
	vis.resize(h,vector<bool>(w,false));
	vis[0][0] = true;
	long long minjoi = first;
	long long maxjoi = first;
	while (!nodes.empty()){
		long long cr = nodes.front().first.first;
		long long cc = nodes.front().first.second;
		long long cval = nodes.front().second.first;
		long long citer = nodes.front().second.second;
		nodes.pop();
		for(auto move : moves){
			long long nr = cr + move.first;
			long long nc = cc + move.second;
			if (nr >= 0 && nr < h && nc >= 0 && nc < w && vis[nr][nc] != true){
				long long newval = grid[nr][nc];
				
			
				long long new_minjoi = min(minjoi, newval);
				long long new_maxjoi = max(maxjoi, newval);
				long long difference = new_maxjoi - new_minjoi;

				if (difference <= mid) {
					// Valid node for JOI region
					minjoi = new_minjoi;
					maxjoi = new_maxjoi;
					vis[nr][nc] = true;
					nodes.push({{nr, nc}, {newval, citer + 1}});
				}

				//else if (difference == mid){
					//auto it = prev(vals.end());
					//auto it2 = vals.begin();
					//long long maxdiff = *it - *it2;
					//nodes.push({{nr,nc},{newval,citer + 1}});
					//return max(difference,maxdiff);
				//}
				
				
			}
			
		}
	}
	//for(int i = 0;i<h;i++){
		
		//bool x = true;
		//for(int j = 0;j<w;j++){
			//if (vis[i][0] == true && vis[i][w-1] == true && vis[i][j] == false && j != w-1){
				//return 1e9;
			//}
			//if (vis[i][w-1] == false && vis[i][0] == false && vis[i][j] == true && j != 0){
				//return 1e9;
			//}
			
			//if (vis[0][j] == true && vis[h-1][j] == true && vis[i][j] == false && i != h-1){
				//return 1e9;
			//}
			//if (vis[h-1][j] == false && vis[0][j] == false && vis[i][j] == true && i != 0){
				//return 1e9;
			//}
		//}
	//}
	if (!is_valid_split(vis)) return 1e9;
	long long minioi = LLONG_MAX, maxioi = LLONG_MIN;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (!vis[i][j]) {
                minioi = min(minioi, grid[i][j]);
                maxioi = max(maxioi, grid[i][j]);
            }
        }
    }
    cout << maxioi << ' ' << minioi << '\n';
	//if (!vals.empty()) {
		//auto it = prev(vals.end());
		//auto it2 = vals.begin();
		//long long maxdiff = abs(*it - *it2);
		//cout << difference << ' ' << maxdiff << '\n';
		//return max(difference, maxdiff);
	//}
	//cout << difference << '\n';
	if (minioi == LLONG_MAX && maxioi == LLONG_MIN) {
   
		return 1e9;
	}
	else if (minioi == LLONG_MAX && maxioi != LLONG_MIN){
		return max(maxjoi - minjoi,0LL);
	}
	else if (minioi != LLONG_MAX && maxioi == LLONG_MIN){
		return max(maxjoi - minjoi, 0LL);
	}
	return max(maxjoi - minjoi, maxioi - minioi);

}

bool check(long long mid){
	
	long long r = bfs(mid);
	return r <= mid;
}
void bsearch(){
	long long lb = 0;
	long long ub = 1e9;
	long long mid = -1;
	long long res = -1;
	while (lb <= ub){
		mid = (lb + ub) / 2;
		if (check(mid)){
			res = mid;
			ub = mid - 1;
		}
		else{
			lb = mid + 1;
		}
	}
	cout << res;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
	cin >> h >> w;
	grid.resize(h,vector<long long>(w));

	
	for(int i = 0;i<h;i++){
		for(int j = 0;j<w;j++){
			long long alt;cin >> alt;
			grid[i][j] = alt;
			ogvals.insert(alt);
		}
	}
	
	bsearch();
}

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