Submission #294320

#	Time	Username	Problem	Language	Result	Execution time	Memory
294320		patrikpavic2	Golf (JOI17_golf)	C++17	30 / 100	477 ms	150012 KiB

golf

#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];
int bio[N][N][4];
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++){
		int kod = 1;
		if(C[i] + 1 < D[i]){
			zabD[A[i]][C[i] + 1] += kod;
			zabD[A[i]][D[i]] -= kod;
			zabD[B[i]][C[i] + 1] -= kod;
			zabD[B[i]][D[i]] += kod;
		}
		if(A[i] + 1 < B[i]){
			zabR[A[i] + 1][C[i]] += kod;
			zabR[A[i] + 1][D[i]] -= kod;
			zabR[B[i]][C[i]] -= kod;
			zabR[B[i]][D[i]] += kod;
		}
	}
	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 + 1 < N && !zabD[nx][ny] && (dis[nx + 1][ny] == -1 || dis[x][y] + 1 == dis[nx + 1][ny]) && !bio[nx + 1][ny][0]){
			nx++;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][0] = 1;
		}
		nx = x, ny = y;
		while(nx > 0 && !zabD[nx - 1][ny] && (dis[nx - 1][ny] == -1 || dis[x][y] + 1 == dis[nx - 1][ny]) && !bio[nx - 1][ny][1]){
			nx--;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][1] = 1;
		}
		nx = x, ny = y;
		while(ny + 1 < N && !zabR[nx][ny] && (dis[nx][ny + 1] == -1 || dis[x][y] + 1 == dis[nx][ny + 1]) && !bio[nx][ny + 1][2]){
			ny++;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][2] = 1;
		}
		nx = x, ny = y;
		while(ny > 0 && !zabR[nx][ny - 1] && (dis[nx][ny - 1] == -1 || dis[x][y] + 1 == dis[nx][ny - 1]) && !bio[nx][ny - 1][3]){
			ny--;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][3] = 1;
		}
	}
	printf("%d\n", dis[t_x][t_y]);
	return 0;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70