oj.uz

Submission #590700

# Submission time Handle Problem Language Result Execution time Memory
590700 2022-07-06T08:53:22 Z 장태환(#8413) Golf (JOI17_golf) C++17
30 / 100
 549 ms 407892 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>xc, yc;
int blk[4010][4010];
int dist[4010][4010][5];
struct bn
{
	int x, y, dir,d;
};
struct ob
{
	int aa, bb, cc, dd;
};
ob arr[2010];
int xo(int n)
{
	return lower_bound(xc.begin(), xc.end(), n) - xc.begin();
}
int yo(int n)
{
	return lower_bound(yc.begin(), yc.end(), n) - yc.begin();
}
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a *= 2;
	b *= 2;
	c *= 2;
	d *= 2;
	int N;
	cin >> N;
	int i;
	for (i = 0; i < N; i++)
	{
		cin >> arr[i].aa >> arr[i].cc >> arr[i].bb >> arr[i].dd;
		arr[i].aa *= 2;
		arr[i].bb *= 2;
		arr[i].cc *= 2;
		arr[i].dd *= 2;
		xc.push_back(arr[i].aa);
		xc.push_back(arr[i].cc);
		xc.push_back(arr[i].aa+1);
		yc.push_back(arr[i].bb);
		yc.push_back(arr[i].dd);
		yc.push_back(arr[i].bb+1);
	}
	xc.push_back(a);
	xc.push_back(c);
	yc.push_back(b);
	yc.push_back(d);
	sort(xc.begin(), xc.end());
	sort(yc.begin(), yc.end());
	xc.erase(unique(xc.begin(), xc.end()), xc.end());
	yc.erase(unique(yc.begin(), yc.end()), yc.end());
	a = xo(a);
	c = xo(c);
	b = yo(b);
	d = yo(d);
	for (i = 0; i < N; i++)
	{
		arr[i].aa = xo(arr[i].aa);
		arr[i].bb = yo(arr[i].bb);
		arr[i].cc = xo(arr[i].cc);
		arr[i].dd = yo(arr[i].dd);
		int j, k;
		for (j = arr[i].aa+1; j < arr[i].cc; j++)
		{
			for (k = arr[i].bb + 1; k < arr[i].dd; k++)
			{
				blk[j][k] = 1;
			}
		}
	}
	memset(dist, 10, sizeof(dist));
	deque<bn>q;
	q.push_back({ a,b,4,0 });
	dist[a][b][4] = 0;
	while (q.size())
	{
		auto t = q.front();
		q.pop_front();
		if (blk[t.x][t.y])
			continue;
		if (t.x == c && t.y == d)
		{
			cout << t.d;
			return 0;
		}
		if (t.dir == 4)
		{
			int j;
			for (j = 0; j < 4; j++)
			{
				if (dist[t.x][t.y][j] > t.d + 1)
				{
					dist[t.x][t.y][j] = t.d + 1;
					q.push_back({ t.x,t.y,j,t.d + 1 });
				}
					
			}
		}
		else
		{
			if (dist[t.x][t.y][4] > t.d)
			{
				dist[t.x][t.y][4] = t.d;
				q.push_front({ t.x,t.y,4,t.d });
			}
				
			t.x += dx[t.dir];
			t.y += dy[t.dir];
			if (t.x < 0 || t.y < 0 || t.x >= xc.size() || t.y >= yc.size())
				continue;
			if (dist[t.x][t.y][t.dir] > t.d)
			{
				dist[t.x][t.y][t.dir] = t.d;
				q.push_front({ t.x,t.y,t.dir,t.d });
			}
			
		}
	}
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:115:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |    if (t.x < 0 || t.y < 0 || t.x >= xc.size() || t.y >= yc.size())
      |                              ~~~~^~~~~~~~~~~~
golf.cpp:115:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |    if (t.x < 0 || t.y < 0 || t.x >= xc.size() || t.y >= yc.size())
      |                                                  ~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 314936 KB Output is correct
2 Correct 126 ms 315016 KB Output is correct
3 Correct 115 ms 315004 KB Output is correct
4 Correct 116 ms 316928 KB Output is correct
5 Correct 211 ms 338964 KB Output is correct
6 Correct 177 ms 333904 KB Output is correct
7 Correct 201 ms 335608 KB Output is correct
8 Correct 187 ms 335312 KB Output is correct
9 Correct 217 ms 334516 KB Output is correct
10 Correct 161 ms 334384 KB Output is correct
11 Correct 182 ms 338288 KB Output is correct
12 Correct 150 ms 333064 KB Output is correct
13 Correct 197 ms 335184 KB Output is correct
14 Correct 189 ms 335564 KB Output is correct
15 Correct 155 ms 319040 KB Output is correct
16 Correct 309 ms 325968 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 314936 KB Output is correct
2 Correct 126 ms 315016 KB Output is correct
3 Correct 115 ms 315004 KB Output is correct
4 Correct 116 ms 316928 KB Output is correct
5 Correct 211 ms 338964 KB Output is correct
6 Correct 177 ms 333904 KB Output is correct
7 Correct 201 ms 335608 KB Output is correct
8 Correct 187 ms 335312 KB Output is correct
9 Correct 217 ms 334516 KB Output is correct
10 Correct 161 ms 334384 KB Output is correct
11 Correct 182 ms 338288 KB Output is correct
12 Correct 150 ms 333064 KB Output is correct
13 Correct 197 ms 335184 KB Output is correct
14 Correct 189 ms 335564 KB Output is correct
15 Correct 155 ms 319040 KB Output is correct
16 Correct 309 ms 325968 KB Output is correct
17 Correct 549 ms 400888 KB Output is correct
18 Correct 462 ms 406772 KB Output is correct
19 Correct 320 ms 381724 KB Output is correct
20 Correct 431 ms 393556 KB Output is correct
21 Correct 425 ms 407892 KB Output is correct
22 Correct 290 ms 391900 KB Output is correct
23 Correct 309 ms 387916 KB Output is correct
24 Correct 523 ms 389216 KB Output is correct
25 Correct 212 ms 374672 KB Output is correct
26 Correct 419 ms 389792 KB Output is correct
27 Correct 166 ms 320108 KB Output is correct
28 Correct 304 ms 327460 KB Output is correct
29 Correct 311 ms 327688 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 314936 KB Output is correct
2 Correct 126 ms 315016 KB Output is correct
3 Correct 115 ms 315004 KB Output is correct
4 Correct 116 ms 316928 KB Output is correct
5 Correct 211 ms 338964 KB Output is correct
6 Correct 177 ms 333904 KB Output is correct
7 Correct 201 ms 335608 KB Output is correct
8 Correct 187 ms 335312 KB Output is correct
9 Correct 217 ms 334516 KB Output is correct
10 Correct 161 ms 334384 KB Output is correct
11 Correct 182 ms 338288 KB Output is correct
12 Correct 150 ms 333064 KB Output is correct
13 Correct 197 ms 335184 KB Output is correct
14 Correct 189 ms 335564 KB Output is correct
15 Correct 155 ms 319040 KB Output is correct
16 Correct 309 ms 325968 KB Output is correct
17 Correct 549 ms 400888 KB Output is correct
18 Correct 462 ms 406772 KB Output is correct
19 Correct 320 ms 381724 KB Output is correct
20 Correct 431 ms 393556 KB Output is correct
21 Correct 425 ms 407892 KB Output is correct
22 Correct 290 ms 391900 KB Output is correct
23 Correct 309 ms 387916 KB Output is correct
24 Correct 523 ms 389216 KB Output is correct
25 Correct 212 ms 374672 KB Output is correct
26 Correct 419 ms 389792 KB Output is correct
27 Correct 166 ms 320108 KB Output is correct
28 Correct 304 ms 327460 KB Output is correct
29 Correct 311 ms 327688 KB Output is correct
30 Runtime error 481 ms 136212 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -