제출 #253288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253288		kostia244	Golf (JOI17_golf)	C++17	0 / 100	396 ms	160464 KiB

golf

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
const int maxn = 4040;
using pt = array<int, 2>;
vector<int> x, y;
int n, dist[maxn][maxn][2], bad[maxn][maxn], a[maxn], b[maxn], c[maxn], d[maxn];
pt st, en;
void inc(int xl, int xr, int yl, int yr) {
	if(xl >= xr || yl >= yr) return;
	bad[xl][yl]++;
	bad[xl][yr]--;
	bad[xr][yl]--;
	bad[xr][yr]++;
}
void dbl(vector<int> &f) {
	vector<int> x;
	for(auto i : f)
		for(int j = 0 ;j < 2; j++)
			x.push_back(i);
	f = x;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> st[0] >> st[1] >> en[0] >> en[1] >> n;
	x.push_back(st[0]);
	x.push_back(en[0]);
	y.push_back(st[1]);
	y.push_back(en[1]);
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		x.push_back(a[i]);
		x.push_back(b[i]);
		y.push_back(c[i]);
		y.push_back(d[i]);
	}
	sort(all(x)), sort(all(y));
	x.erase(unique(all(x)), x.end());
	y.erase(unique(all(y)), y.end());
	dbl(x), dbl(y);
	st[0] = lower_bound(all(x), st[0]) - x.begin();
	st[1] = lower_bound(all(y), st[1]) - y.begin();
	en[0] = lower_bound(all(x), en[0]) - x.begin();
	en[1] = lower_bound(all(y), en[1]) - y.begin();
	for(int i = 0; i < n; i++) {
		a[i] = lower_bound(all(x), a[i]) - x.begin();
		b[i] = upper_bound(all(x), b[i]) - x.begin() - 1;
		c[i] = lower_bound(all(y), c[i]) - y.begin();
		d[i] = upper_bound(all(y), d[i]) - y.begin() - 1;
		inc(a[i]+1, b[i], c[i]+1, d[i]);
	}
	for(int i = 0; i < x.size(); i++) {
		for(int j = 0; j < y.size(); j++) {
			if(i) bad[i][j] += bad[i-1][j];
			if(j) bad[i][j] += bad[i][j-1];
			if(i&&j) bad[i][j] -= bad[i-1][j-1];
		}
	}
	vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
	priority_queue<array<ll, 4>> pq;
	memset(dist, 0x3f, sizeof dist);
	dist[st[0]][st[1]][0] = 1;
	dist[st[0]][st[1]][1] = 1;
	pq.push({-1, 0, st[0], st[1]});
	pq.push({-1, 1, st[0], st[1]});
	while(!pq.empty()) {
		auto [d, dir, X, Y] = pq.top();
		pq.pop();
		d *= -1;
		if(d > dist[X][Y][dir]) continue;
		if(X-(X&1) == en[0] && Y-(Y&1) == en[1]) return cout << d << '\n', 0;
		for(int i = 0; i < 4; i++) {
			int tx = X + dx[i], ty = Y + dy[i], tdir = i/2;
			if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
			ll c = d + (dir != tdir);
			if(c < dist[tx][ty][tdir]) {
				dist[tx][ty][tdir] = c;
				pq.push({-c, tdir, tx, ty});
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

golf.cpp: In function 'int main()':
golf.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < x.size(); i++) {
                 ~~^~~~~~~~~~
golf.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < y.size(); j++) {
                  ~~^~~~~~~~~~
golf.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
                 ~~~^~~~~~~~~~~
golf.cpp:76:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
                                             ~~~^~~~~~~~~~~

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