Submission #515056

#	Time	Username	Problem	Language	Result	Execution time	Memory
515056		amunduzbaev	Golf (JOI17_golf)	C++14	30 / 100	2162 ms	136824 KiB

golf

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e3 + 5;
int g[N][N][4];
int d[N][N][4];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	ar<int, 2> a, b; cin>>a[0]>>a[1]>>b[0]>>b[1];
	int n; cin>>n;
	vector<ar<int, 4>> p(n);
	for(int i=0;i<n;i++){
		cin>>p[i][0]>>p[i][2]>>p[i][1]>>p[i][3];
	}
	
	vector<ar<int, 2>> tt;
	for(int i=0;i<n;i++){
		tt.push_back({p[i][0], i<<1});
		tt.push_back({p[i][2], i<<1|1});
	} 
	tt.push_back({a[0], -1});
	tt.push_back({b[0], -2});
	sort(tt.begin(), tt.end());
	
	int last = 0;
	for(int i=0;i<(int)tt.size();){
		int j = i;
		while(j < (int)tt.size() && tt[i][0] == tt[j][0]){
			if(tt[j][1]>=0) p[tt[j][1]>>1][(tt[j][1]&1) << 1] = last;
			else if(tt[j][1]==-1) a[0] = last;
			else b[0] = last;
			j++;
		} i = j, last++;
	} tt.clear();
	
	for(int i=0;i<n;i++){
		tt.push_back({p[i][1], i<<1});
		tt.push_back({p[i][3], i<<1|1});
	} 
	tt.push_back({a[1], -1});
	tt.push_back({b[1], -2});
	
	sort(tt.begin(), tt.end());
	last = 0;
	for(int i=0;i<(int)tt.size();){
		int j = i;
		while(j < (int)tt.size() && tt[j][0] == tt[i][0]){
			if(tt[j][1] >= 0) p[tt[j][1]>>1][(tt[j][1]&1)<<1|1] = last;
			else if(tt[j][1] == -1) a[1] = last;
			else b[1] = last;
			j++;
		} last++, i = j;
	}
	
	int ch[4][2] = {
		{0, 1},
		{0, -1},
		{1, 0},
		{-1, 0}
	};
	
	for(int k=0;k<n;k++){
		for(int i=p[k][0];i<=p[k][2];i++){
			for(int j=p[k][1];j<=p[k][3];j++){
				for(int t=0;t<4;t++){
					int x = i+ch[t][0], y = j+ch[t][1];
					if(p[k][0] <= x && x <= p[k][2] && 
					   p[k][1] <= y && y <= p[k][3]){
						if(x == i && (i == p[k][0] || i == p[k][2])) continue;
						if(y == j && (j == p[k][1] || j == p[k][3])) continue;
						g[i][j][t] = 1;
					}
				}
			}
		}
	}
	
	auto check = [&](int x, int y){ return (0 <= x && x < N && 0 <= y && y < N); };
	memset(d, 2, sizeof d);
	deque<int> qq;
	for(int t=0;t<4;t++){
		qq.push_back((a[0] * N + a[1]) << 2 | t);
		d[a[0]][a[1]][t] = 1;	
	}
	
	while(!qq.empty()){
		int u = qq.front(); qq.pop_front(); 
		int t = u & 3; u >>= 2;
		int i = u / N, j = u % N;
		//~ cout<<i<<" "<<j<<" "<<t<<"\n";
		if(!g[i][j][t]){
			int x = i + ch[t][0], y = j + ch[t][1];
			if(check(x, y) && d[x][y][t] > d[i][j][t]){
				d[x][y][t] = d[i][j][t];
				qq.push_front((x * N + y) << 2 | t);
			}
		}
		
		for(int k=0;k<4;k++){
			if(g[i][j][k]) continue;
			int x = i + ch[k][0], y = j + ch[k][1];
			if(check(x, y) && d[x][y][k] > d[i][j][t] + 1){
				d[x][y][k] = d[i][j][t] + 1;
				qq.push_back((x * N + y) << 2 | k);
			}
		}
	}
	
	int res = 1e9;
	for(int t=0;t<4;t++) res = min(res, d[b[0]][b[1]][t]);
	cout<<res<<"\n";
}

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