Submission #26560

#	Time	Username	Problem	Language	Result	Execution time	Memory
26560		gs14004	Golf (JOI17_golf)	C++14	30 / 100	1242 ms	114752 KiB

golf

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

int n;
pi s, e;
struct rect{ int sx, ex, sy, ey; }a[1005];

int sx, sy, xe[2048][2048], ye[2048][2048];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bool vis[2048][2048][4];

int ok(int x, int y, int d){
	if(vis[x][y][d]) return 0;
	if(d == 0){
		return x + 1 < sx && xe[x+1][y] == 0;
	}
	if(d == 1){
		return y + 1 < sy && ye[x][y+1] == 0;
	}
	if(d == 2){
		return x - 1 >= 0 && xe[x][y] == 0;	
	}
	if(d == 3){
		return y - 1 >= 0 && ye[x][y] == 0;
	}
	assert(0);
}

struct node{
	int x, y, d, cost;
	bool operator<(const node &n)const{
		return cost > n.cost;
	}
};

int solve(){
	priority_queue<node> que;
	memset(vis, 0, sizeof(vis));
	for(int i=0; i<4; i++){
		if(ok(s.first, s.second, i)){
			que.push({s.first, s.second, i, 1});
		}
	}
	while(!que.empty()){
		auto x = que.top();
		que.pop();
		if(vis[x.x][x.y][x.d]) continue;
		vis[x.x][x.y][x.d] = 1;
		x.x += dx[x.d];
		x.y += dy[x.d];
		if(pi(x.x, x.y) == e){
			return x.cost;
		}
		for(int i=0; i<4; i++){
			if(ok(x.x, x.y, i)){
				que.push({x.x, x.y, i, x.cost + (i != x.d)});
			}
		}
	}
	return 1e9;
}

int main(){
	cin >> s.first >> s.second >> e.first >> e.second >> n;
	if(n > 1000){
		puts("I want to go to IOI2017 TT");
		return 0;
	}
	vector<int> vx = {s.first, e.first}, vy = {s.second, e.second};
	for(int i=0; i<n; i++){
		scanf("%d %d %d %d",&a[i].sx,&a[i].ex,&a[i].sy,&a[i].ey);
		vx.push_back(a[i].sx);
		vx.push_back(a[i].ex);
		vy.push_back(a[i].sy);
		vy.push_back(a[i].ey);
	}
	sort(vx.begin(), vx.end());
	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
	sort(vy.begin(), vy.end());
	vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
	auto getloc = [&](int x, vector<int> &v){
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	};
	s.first = getloc(s.first, vx);
	s.second = getloc(s.second, vy);
	e.first = getloc(e.first, vx);
	e.second = getloc(e.second, vy);
	for(int i=0; i<n; i++){
		a[i].sx = getloc(a[i].sx, vx);
		a[i].ex = getloc(a[i].ex, vx);
		a[i].sy = getloc(a[i].sy, vy);
		a[i].ey = getloc(a[i].ey, vy);
	}
	sx = vx.size();
	sy = vy.size();
	for(int i=0; i<n; i++){
		xe[a[i].sx + 1][a[i].sy + 1]++;
		xe[a[i].ex + 1][a[i].sy + 1]--;
		xe[a[i].sx + 1][a[i].ey]--;
		xe[a[i].ex + 1][a[i].ey]++;
		ye[a[i].sx + 1][a[i].sy + 1]++;
		ye[a[i].sx + 1][a[i].ey + 1]--;
		ye[a[i].ex][a[i].sy + 1]--;
		ye[a[i].ex][a[i].ey + 1]++;
	}
	for(int i=1; i<sx; i++){
		for(int j=1; j<sy; j++){
			xe[i][j] += xe[i-1][j] + xe[i][j-1] - xe[i-1][j-1];
			ye[i][j] += ye[i-1][j] + ye[i][j-1] - ye[i-1][j-1];
		}
	}
  	cout << solve();
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a[i].sx,&a[i].ex,&a[i].sy,&a[i].ey);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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