답안 #294314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
294314 2020-09-08T19:08:26 Z patrikpavic2 Golf (JOI17_golf) C++17
0 / 100
385 ms 84152 KB
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
 
#define X first
#define Y second
#define PB push_back
 
using namespace std;
 
typedef pair < int, int > pt;
 
const int N = 2e3 + 50;
 
int n, s_x, s_y, t_x, t_y;
int A[N], B[N], C[N], D[N], dis[N][N], zabD[N][N], zabR[N][N];
vector < int > sazx, sazy;
 
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
 
int nadi(int x, vector < int > &v){
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
 
int main(){
	memset(dis, -1, sizeof(dis));
	scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
	sazx.PB(s_x); sazx.PB(t_x);
	sazy.PB(s_y); sazy.PB(t_y);
	for(int i = 0;i < n;i++){
		scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
		sazx.PB(A[i]); sazx.PB(B[i]);
		sazy.PB(C[i]); sazy.PB(D[i]);
	}
	sort(sazx.begin(), sazx.end());
	sort(sazy.begin(), sazy.end());
	sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
	sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
	s_x = nadi(s_x, sazx); 	t_x = nadi(t_x, sazx);
	s_y = nadi(s_y, sazy); 	t_y = nadi(t_y, sazy);
	for(int i = 0;i < n;i++){
		A[i] = nadi(A[i], sazx); B[i] = nadi(B[i], sazx);
		C[i] = nadi(C[i], sazy); D[i] = nadi(D[i], sazy);
	}
	for(int i = 0;i < n;i++){
		if(C[i] + 1 < D[i]){
			zabD[A[i]][C[i] + 1]++;
			zabD[A[i]][D[i]]--;
			zabD[B[i]][C[i] + 1]--;
			zabD[B[i]][D[i]]++;
		}
		if(A[i] + 1 < B[i]){
			zabR[A[i] + 1][C[i]]++;
			zabR[A[i] + 1][D[i]]--;
			zabR[B[i]][C[i]]--;
			zabR[B[i]][D[i]]++;
		}
	}
	for(int i = 0;i < N;i++){
		for(int j = 1;j < N;j++){
			zabD[i][j] += zabD[i][j - 1];
			zabR[i][j] += zabR[i][j - 1];
		}
	}
	for(int i = 1;i < N;i++){
		for(int j = 0;j < N;j++){
			zabD[i][j] += zabD[i - 1][j];
			zabR[i][j] += zabR[i - 1][j];
		}
	}
	queue < pt > Q;
	Q.push({s_x, s_y}); dis[s_x][s_y] = 0; 
	for(;!Q.empty();Q.pop()){
		int x = Q.front().X, y = Q.front().Y;
		int nx = x, ny = y;
		while(nx < N && !zabD[nx][ny] && dis[nx + 1][ny] == -1){
			dis[nx + 1][ny] = dis[x][y] + 1;
			Q.push({nx + 1, ny}); nx++;
		}
		nx = x, ny = y;
		while(nx > 0 && !zabD[nx - 1][ny] && dis[nx - 1][ny] == -1){
			dis[nx - 1][ny] = dis[x][y] + 1;
			Q.push({nx - 1, ny}); nx--;		
		}
		nx = x, ny = y;
		while(ny < N && !zabR[nx][ny] && dis[nx][ny + 1] == -1){
			dis[nx][ny + 1] = dis[x][y] + 1;
			Q.push({nx, ny + 1}); ny++;
		}
		nx = x, ny = y;
		while(ny > 0 && !zabR[nx][ny - 1] && dis[nx][ny - 1] == -1){
			dis[nx][ny - 1] = dis[x][y] + 1;
			Q.push({nx, ny - 1}); ny--;		
		}
	}
	printf("%d\n", dis[t_x][t_y]);
	return 0;
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 84152 KB Output is correct
2 Incorrect 385 ms 84092 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 84152 KB Output is correct
2 Incorrect 385 ms 84092 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 84152 KB Output is correct
2 Incorrect 385 ms 84092 KB Output isn't correct
3 Halted 0 ms 0 KB -