oj.uz

답안 #39557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39557 2018-01-16T13:48:58 Z comtalyst The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 3 ms 25572 KB 
/*
 *	Task: JOI17_JOIOI
 *	Lang: C/C++11
 *	Author: comtalyst
 *	Site: oj.uz
 *	Last Update: 16/1/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)2e9
#define MIN (int)-2e9
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

bool chk[2][2005][2005];
int n,m,field[2005][2005];
pair<int,int> dr[]={{1,0},{0,1},{-1,0},{0,-1}};
bool valid(bool t,int x,int y){
	if(x < 1 || y < 1 || x > n || y > m){
		return false;
	}
	if(!chk[t][x][y]){
		chk[t][x][y] = true;
		return true;
	}
	return false;
}


main(){
	int t,i,j,x,y,l,r,mid,res=MAX,nx,ny;
	bool ok;
	queue<pair<int,int>> q;
	pair<int,pair<int,int>> mn={MAX,{MAX,MAX}},mx={MIN,{MIN,MIN}};
	
	scanf("%d %d",&n,&m);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			scanf("%d",&field[i][j]);
			mn = min(mn,{field[i][j],{i,j}});
			mx = max(mx,{field[i][j],{i,j}});
		}
	}
	l = 0; 
	r = mx.x-mn.x;
	while(l <= r){
		mid = (l+r)/2;
		memset(chk,0,sizeof chk);
		chk[0][mn.y.x][mn.y.y] = true;
		q.emplace(mn.y.x,mn.y.y);
		while(!q.empty()){
			x = q.front().x;
			y = q.front().y;
			q.pop();
			for(i = 0; i < 4; i++){
				nx = x + dr[i].x;
				ny = y + dr[i].y;
				if(field[nx][ny] - mn.x <= mid && valid(0,nx,ny)){
					q.emplace(nx,ny);
				}
			}
		}
		chk[1][mx.y.x][mx.y.y] = true;
		q.emplace(mx.y.x,mx.y.y);
		while(!q.empty()){
			x = q.front().x;
			y = q.front().y;
			q.pop();
			for(i = 0; i < 4; i++){
				nx = x + dr[i].x;
				ny = y + dr[i].y;
				if(mx.x - field[nx][ny] <= mid && valid(1,nx,ny)){
					q.emplace(nx,ny);
				}
			}
		}
/*		printf(">> %d\n",mid);
		for(i = 1; i <= n; i++){
			for(j = 1; j <= m; j++){
				printf("%d ",(int)chk[0][i][j] + (int)chk[1][i][j]);
			}
			printf("\n");
		}*/
		ok = true;
		for(i = 1; i <= n && ok; i++){
			for(j = 1; j <= m; j++){
				if(!chk[0][i][j] && !chk[1][i][j]){
					ok = false;
					break;
				}
			}
		}
		if(ok){
			res = min(res,mid);
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	printf("%d\n",res);

	return 0;	
}

Compilation message

joioi.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:53:6: warning: unused variable 't' [-Wunused-variable]
  int t,i,j,x,y,l,r,mid,res=MAX,nx,ny;
      ^
joioi.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
joioi.cpp:61:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&field[i][j]);
                            ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 25572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 25572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 25572 KB Output isn't correct
2 Halted 0 ms 0 KB -