oj.uz

Submission #826819

# Submission time Handle Problem Language Result Execution time Memory
826819 2023-08-16T05:00:12 Z 반딧불(#10373) Golf (JOI17_golf) C++17
0 / 100
 182 ms 83912 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Rect{
	int xl, yl, xr, yr;
	Rect(){}
	Rect(int xl, int yl, int xr, int yr): xl(xl), yl(yl), xr(xr), yr(yr){}
};

int xs, ys, xe, ye;
int n;
Rect rects[100002];

void renumber();
void solve();

int main(){
	scanf("%d %d %d %d %d", &xs, &ys, &xe, &ye, &n);
	for(int i=1; i<=n; i++){
		scanf("%d %d %d %d", &rects[i].xl, &rects[i].xr, &rects[i].yl, &rects[i].yr);
	}

	//renumber();
	solve();
}

int H, W;

void renumber(){
	vector<int> vx, vy;
	vx.push_back(xs), vx.push_back(xe), vy.push_back(ys), vy.push_back(ye);
	for(int i=1; i<=n; i++){
		vx.push_back(rects[i].xl), vx.push_back(rects[i].xr);
		vy.push_back(rects[i].yl), vy.push_back(rects[i].yr);
	}
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	sort(vy.begin(), vy.end());
	vy.erase(unique(vy.begin(), vy.end()), vy.end());
	H = (int)vx.size();
	W = (int)vy.size();
	xs = lower_bound(vx.begin(), vx.end(), xs) - vx.begin() + 1;
	xe = lower_bound(vx.begin(), vx.end(), xe) - vx.begin() + 1;
	ys = lower_bound(vy.begin(), vy.end(), ys) - vy.begin() + 1;
	ye = lower_bound(vy.begin(), vy.end(), ye) - vy.begin() + 1;
	for(int i=1; i<=n; i++){
		rects[i].xl = lower_bound(vx.begin(), vx.end(), rects[i].xl) - vx.begin() + 1;
		rects[i].xr = lower_bound(vx.begin(), vx.end(), rects[i].xr) - vx.begin() + 1;
		rects[i].yl = lower_bound(vy.begin(), vy.end(), rects[i].yl) - vy.begin() + 1;
		rects[i].yr = lower_bound(vy.begin(), vy.end(), rects[i].yr) - vy.begin() + 1;
	}
}

struct dat{
	int x, y, dir, dist;
	dat(){}
	dat(int x, int y, int dir, int dist): x(x), y(y), dir(dir), dist(dist){}
};

const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
deque<dat> dq;
bool visited[2102][2102][4];
int dist[2102][2102][4];
bool passable[2102][2102][4];

void solve(){
	H=1000, W=1000;
	for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) for(int d=0; d<4; d++) passable[i][j][d] = 1;
	for(int i=1; i<=n; i++){
		int xl = rects[i].xl, xr = rects[i].xr, yl = rects[i].yl, yr = rects[i].yr;
		for(int x=xl+1; x<xr; x++) for(int y=yl; y<yr; y++) passable[x][y][0] = false;
		for(int x=xl; x<xr; x++) for(int y=yl+1; y<yr; y++) passable[x][y][1] = false;
		for(int x=xl+1; x<xr; x++) for(int y=yl+1; y<=yr; y++) passable[x][y][2] = false;
		for(int x=xl+1; x<=xr; x++) for(int y=yl+1; y<yr; y++) passable[x][y][3] = false;
	}

	for(int i=0; i<4; i++) dq.push_back(dat(xs, ys, i, 1));
	while(!dq.empty()){
		dat tmp = dq.front(); dq.pop_front();
		if(visited[tmp.x][tmp.y][tmp.dir]) continue;
		visited[tmp.x][tmp.y][tmp.dir] = 1;
		dist[tmp.x][tmp.y][tmp.dir] = tmp.dist;
		//printf("%d %d %d: %d\n", tmp.x, tmp.y, tmp.dir, tmp.dist);
		if(tmp.x == xe && tmp.y == ye){
			printf("%d", tmp.dist);
			exit(0);
		}
		for(int d=0; d<4; d++){
			int tx = tmp.x + xx[d], ty = tmp.y + yy[d];
			if(tx<1 || tx>H || ty<1 || ty>W || !passable[tx][ty][d]) continue;
			if(d == tmp.dir) dq.push_front(dat(tx, ty, d, tmp.dist));
			else dq.push_back(dat(tx, ty, d, tmp.dist+1));
		}
	}
	printf("-1");
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d %d %d %d %d", &xs, &ys, &xe, &ye, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d %d %d %d", &rects[i].xl, &rects[i].xr, &rects[i].yl, &rects[i].yr);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 52480 KB Output is correct
2 Correct 33 ms 41492 KB Output is correct
3 Correct 62 ms 64212 KB Output is correct
4 Correct 20 ms 26212 KB Output is correct
5 Correct 64 ms 47504 KB Output is correct
6 Correct 46 ms 43860 KB Output is correct
7 Correct 71 ms 43948 KB Output is correct
8 Correct 61 ms 44912 KB Output is correct
9 Correct 61 ms 41856 KB Output is correct
10 Correct 30 ms 28948 KB Output is correct
11 Correct 31 ms 39096 KB Output is correct
12 Correct 24 ms 24844 KB Output is correct
13 Correct 60 ms 44388 KB Output is correct
14 Correct 51 ms 40140 KB Output is correct
15 Incorrect 182 ms 83912 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 52480 KB Output is correct
2 Correct 33 ms 41492 KB Output is correct
3 Correct 62 ms 64212 KB Output is correct
4 Correct 20 ms 26212 KB Output is correct
5 Correct 64 ms 47504 KB Output is correct
6 Correct 46 ms 43860 KB Output is correct
7 Correct 71 ms 43948 KB Output is correct
8 Correct 61 ms 44912 KB Output is correct
9 Correct 61 ms 41856 KB Output is correct
10 Correct 30 ms 28948 KB Output is correct
11 Correct 31 ms 39096 KB Output is correct
12 Correct 24 ms 24844 KB Output is correct
13 Correct 60 ms 44388 KB Output is correct
14 Correct 51 ms 40140 KB Output is correct
15 Incorrect 182 ms 83912 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 52480 KB Output is correct
2 Correct 33 ms 41492 KB Output is correct
3 Correct 62 ms 64212 KB Output is correct
4 Correct 20 ms 26212 KB Output is correct
5 Correct 64 ms 47504 KB Output is correct
6 Correct 46 ms 43860 KB Output is correct
7 Correct 71 ms 43948 KB Output is correct
8 Correct 61 ms 44912 KB Output is correct
9 Correct 61 ms 41856 KB Output is correct
10 Correct 30 ms 28948 KB Output is correct
11 Correct 31 ms 39096 KB Output is correct
12 Correct 24 ms 24844 KB Output is correct
13 Correct 60 ms 44388 KB Output is correct
14 Correct 51 ms 40140 KB Output is correct
15 Incorrect 182 ms 83912 KB Output isn't correct
16 Halted 0 ms 0 KB -