Submission #709350

#	Time	Username	Problem	Language	Result	Execution time	Memory
709350		Antekb	Golf (JOI17_golf)	C++17	30 / 100	563 ms	91752 KiB

golf

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int N=2005, INF=1e9+5;
int d[N][N], czy[N][N][4];
vector<pii> edg={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main(){
	map<int, int> Mx, My;
	int xp, yp, xk, yk;
	cin>>xp>>yp>>xk>>yk;
	Mx[xp]=1;
	My[yp]=1;
	Mx[xk]=1;
	My[yk]=1;
	int n;
	cin>>n;
	vector<pair<pii, pii> > rec(n);
	for(int i=0; i<n; i++){
		cin>>rec[i].st.st>>rec[i].st.nd>>rec[i].nd.st>>rec[i].nd.nd;
		Mx[rec[i].st.st]=1;
		Mx[rec[i].st.nd]=1;
		My[rec[i].nd.st]=1;
		My[rec[i].nd.nd]=1;
	}
	int wskx=0;
	for(auto &i:Mx){
		i.nd=wskx++;
	}
	xp=Mx[xp];
	xk=Mx[xk];
	for(int i=0; i<n; i++){
		rec[i].st.st=Mx[rec[i].st.st];
		rec[i].st.nd=Mx[rec[i].st.nd];
	}
	int wsky=0;
	for(auto &i:My){
		i.nd=wsky++;
	}
	yp=My[yp];
	yk=My[yk];
	for(int i=0; i<n; i++){
		rec[i].nd.st=My[rec[i].nd.st];
		rec[i].nd.nd=My[rec[i].nd.nd];
	}
	for(int i=0; i<wskx; i++){
		for(int j=0; j<wsky; j++){
			for(int k=0; k<4; k++){
				d[i][j]=1e9;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=rec[i].st.st+1; j<=rec[i].st.nd-1; j++){	
			czy[j][rec[i].nd.st][1]=1;
			czy[j][rec[i].nd.nd][3]=1;
		}
		for(int k=rec[i].nd.st+1; k<=rec[i].nd.nd-1; k++){
			czy[rec[i].st.st][k][0]=1;
			czy[rec[i].st.nd][k][2]=1;
		}
	}
	//deb(xp, yp);
	//deb(xk, yk);
	//deb(rec[0].st.st, rec[0].st.nd, rec[0].nd.st, rec[0].nd.nd);
	vector<pair<int, int> > V;
	d[xp][yp]=0;
	V.eb(xp, yp);
	//deb(wskx, wsky);
	for(int i=0; i<V.size(); i++){
		int x=V[i].st, y=V[i].nd;
		//deb(x, y, d[x][y]);
		int dist=d[x][y];
		for(int xx=x+1; xx<wskx; xx++){
			if(d[xx][y]<=dist || czy[xx-1][y][0])break;
			//deb(xx, y);
			if(d[xx][y]>dist+1)d[xx][y]=dist+1, V.eb(xx, y);
		}
		for(int xx=x-1; xx>=0; xx--){
			if(d[xx][y]<=dist || czy[xx+1][y][2])break;
			if(d[xx][y]>dist+1)d[xx][y]=dist+1, V.eb(xx, y);
		}
		
		for(int yy=y+1; yy<wsky; yy++){
			if(d[x][yy]<=dist || czy[x][yy-1][1])break;
			if(d[x][yy]>dist+1)d[x][yy]=dist+1, V.eb(x, yy);
		}
		for(int yy=y-1; yy>=0; yy--){
			if(d[x][yy]<=dist || czy[x][yy+1][3])break;
			if(d[x][yy]>dist+1)d[x][yy]=dist+1, V.eb(x, yy);
		}
	}
	cout<<d[xk][yk];
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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