Submission #1003534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003534		jamjanek	Golf (JOI17_golf)	C++14	30 / 100	10055 ms	41460 KiB

golf

#include<bits/stdc++.h>
using namespace std;
map<int,int>mapx, mapy;
struct rect{int a, b, c, d; int id;};
vector<rect>pros;
bool cmp1(rect a, rect b){
	return a.a < b.a;
}

bool cmp2(rect a, rect b){
	return a.c < b.c;
}
bool cmp3(rect a, rect b){
	return a.b > b.b;
}
bool cmp4(rect a, rect b){
	return a.d > b.d;
}
struct oX{int x, p, k, id, dist;};
struct oY{int y, p, k, id, dist;};
oX oXs[400010];
oY oYs[400010];
bool przecina(int x, int y){
	if(oXs[x].p<=oYs[y].y && oXs[x].k>=oYs[y].y && oYs[y].p<=oXs[x].x && oYs[y].k>=oXs[x].x)
		return 1;
	return 0;
}
const int base = 1<<18;
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int val){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w] = val;
		return;
	}
	if(tree[w]!=-1)
		tree[w*2] = tree[w*2+1] = tree[w];
	tree[w] = -1;
	ustaw(w*2, l, (l+p)/2, a, b, val);
	ustaw(w*2+1, (l+p)/2+1, p, a, b, val);
}
int value(int w){
	int ans = -1;
	w+=base;
	while(w>0){
		if(tree[w]!=-1)
			ans = tree[w];
		w/=2;
	}
	return ans;
}
int main()
{
	int sx, sy, tx, ty, n, i;
	scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
	mapx[sx]=0;
	mapx[tx]=0;
	mapy[sy]=0;
	mapy[ty]=0;
	for(i=0;i<n;i++){
		pros.push_back({});
		scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
		mapx[pros.back().a] = mapx[pros.back().b] = 0;
		mapy[pros.back().c] = mapy[pros.back().d] = 0;
	}
	i = 0;
	for(auto &ij: mapx)
		ij.second = i++;
	i = 0;
	for(auto &ij: mapy)
		ij.second = i++;
	sx = mapx[sx];
	tx = mapx[tx];
	sy = mapy[sy];
	ty = mapy[ty];
	for(auto &ij: pros){
		ij.a = mapx[ij.a];
		ij.b = mapx[ij.b];
		ij.c = mapy[ij.c];
		ij.d = mapy[ij.d];
	}
	pros.push_back({sx, sx, sy, sy});//start ma id n
	pros.push_back({tx, tx, ty, ty});//koniec ma id n+1
	for(i=0;i<n+2;i++){
		pros[i].id = i;
		oXs[i*4+0].x = pros[i].a;
		oYs[i*4+1].y = pros[i].c;
		oXs[i*4+2].x = pros[i].b;
		oYs[i*4+3].y = pros[i].d;
	}
	sort(pros.begin(), pros.end(), cmp1);
	ustaw(1, 0, base-1, 0, 2*(n+1), 0);
	for(auto &ij: pros){
		oYs[ij.id*4+1].p = value(ij.c);
		oYs[ij.id*4+3].p = value(ij.d);
		ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.b);
	}
	sort(pros.begin(), pros.end(), cmp2);
	ustaw(1, 0, base-1, 0, 2*(n+1), 0);
	for(auto &ij: pros){
		oXs[ij.id*4+0].p = value(ij.a);
		oXs[ij.id*4+2].p = value(ij.b);
		ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.d);
	}
	sort(pros.begin(), pros.end(), cmp3);
	ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
	for(auto &ij: pros){
		oYs[ij.id*4+1].k = value(ij.c);
		oYs[ij.id*4+3].k = value(ij.d);
		ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.a);
	}
	sort(pros.begin(), pros.end(), cmp4);
	ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
	for(auto &ij: pros){
		oXs[ij.id*4+0].k = value(ij.a);
		oXs[ij.id*4+2].k = value(ij.b);
		ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.c);
	}
	
	if(sx==tx){
		if(oXs[n*4+0].p<=ty && oXs[n*4+0].k>=ty){
			printf("1\n");return 0;
		}
	}
	
	if(sy==ty){
		if(oYs[n*4+1].p<=tx && oYs[n*4+1].k>=tx){
			printf("1\n");return 0;
		}
	}
	queue<int>kolejka;
	oXs[n*4+0].dist = 1;
	oXs[n*4+2].dist = 1;
	oYs[n*4+1].dist = 1;
	oYs[n*4+3].dist = 1;
	kolejka.push(n*4+0);
	kolejka.push(n*4+1);
	kolejka.push(n*4+2);
	kolejka.push(n*4+3);
	while(kolejka.size()){
		auto ij = kolejka.front();
		kolejka.pop();
		if(ij%2==0){
			for(i=1;i<(n+1)*4+4;i+=2){
				if(przecina(ij, i) && oYs[i].dist==0){
					oYs[i].dist = oXs[ij].dist+1;
					kolejka.push(i);
				}
			}
		}
		else{
			for(i=0;i<(n+1)*4+4;i+=2){
				if(przecina(i, ij) && oXs[i].dist==0){
					oXs[i].dist = oYs[ij].dist+1;
					kolejka.push(i);
				}
			}			
		}
	}
	printf("%d\n", min({oXs[(n+1)*4+0].dist, oXs[(n+1)*4+2].dist, oYs[(n+1)*4+1].dist, oYs[(n+1)*4+3].dist}));
	/*
	printf("X:\n");
	for(i=0;i<=(n+1);i++){
		printf("%d %d %d %d %d\n", oXs[i*4+0].x, oXs[i*4+0].p, oXs[i*4+0].k, oXs[i*4+0].id, oXs[i*4+0].dist);
		printf("%d %d %d %d %d\n", oXs[i*4+2].x, oXs[i*4+2].p, oXs[i*4+2].k, oXs[i*4+2].id, oXs[i*4+2].dist);
	}
	printf("Y:\n");
	for(i=0;i<=(n+1);i++){
		printf("%d %d %d %d %d\n", oYs[i*4+1].y, oYs[i*4+1].p, oYs[i*4+1].k, oYs[i*4+1].id, oYs[i*4+1].dist);
		printf("%d %d %d %d %d\n", oYs[i*4+3].y, oYs[i*4+3].p, oYs[i*4+3].k, oYs[i*4+3].id, oYs[i*4+3].dist);
	}*/
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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