oj.uz

Submission #294320

# Submission time Handle Problem Language Result Execution time Memory
294320 2020-09-08T19:10:08 Z patrikpavic2 Golf (JOI17_golf) C++17
30 / 100
 477 ms 150012 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
 
#define X first
#define Y second
#define PB push_back
 
using namespace std;
 
typedef pair < int, int > pt;
 
const int N = 2e3 + 50;
 
int n, s_x, s_y, t_x, t_y;
int A[N], B[N], C[N], D[N], dis[N][N], zabD[N][N], zabR[N][N];
int bio[N][N][4];
vector < int > sazx, sazy;
 
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
 
int nadi(int x, vector < int > &v){
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
 
int main(){
	memset(dis, -1, sizeof(dis));
	scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
	sazx.PB(s_x); sazx.PB(t_x);
	sazy.PB(s_y); sazy.PB(t_y);
	for(int i = 0;i < n;i++){
		scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
		sazx.PB(A[i]); sazx.PB(B[i]);
		sazy.PB(C[i]); sazy.PB(D[i]);
	}
	sort(sazx.begin(), sazx.end());
	sort(sazy.begin(), sazy.end());
	sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
	sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
	s_x = nadi(s_x, sazx); 	t_x = nadi(t_x, sazx);
	s_y = nadi(s_y, sazy); 	t_y = nadi(t_y, sazy);
	for(int i = 0;i < n;i++){
		A[i] = nadi(A[i], sazx); B[i] = nadi(B[i], sazx);
		C[i] = nadi(C[i], sazy); D[i] = nadi(D[i], sazy);
	}
	for(int i = 0;i < n;i++){
		int kod = 1;
		if(C[i] + 1 < D[i]){
			zabD[A[i]][C[i] + 1] += kod;
			zabD[A[i]][D[i]] -= kod;
			zabD[B[i]][C[i] + 1] -= kod;
			zabD[B[i]][D[i]] += kod;
		}
		if(A[i] + 1 < B[i]){
			zabR[A[i] + 1][C[i]] += kod;
			zabR[A[i] + 1][D[i]] -= kod;
			zabR[B[i]][C[i]] -= kod;
			zabR[B[i]][D[i]] += kod;
		}
	}
	for(int i = 0;i < N;i++){
		for(int j = 1;j < N;j++){
			zabD[i][j] += zabD[i][j - 1];
			zabR[i][j] += zabR[i][j - 1];
		}
	}
	for(int i = 1;i < N;i++){
		for(int j = 0;j < N;j++){
			zabD[i][j] += zabD[i - 1][j];
			zabR[i][j] += zabR[i - 1][j];
		}
	}
	queue < pt > Q;
	Q.push({s_x, s_y}); dis[s_x][s_y] = 0; 
	for(;!Q.empty();Q.pop()){
		int x = Q.front().X, y = Q.front().Y;
		int nx = x, ny = y;
		while(nx + 1 < N && !zabD[nx][ny] && (dis[nx + 1][ny] == -1 || dis[x][y] + 1 == dis[nx + 1][ny]) && !bio[nx + 1][ny][0]){
			nx++;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][0] = 1;
		}
		nx = x, ny = y;
		while(nx > 0 && !zabD[nx - 1][ny] && (dis[nx - 1][ny] == -1 || dis[x][y] + 1 == dis[nx - 1][ny]) && !bio[nx - 1][ny][1]){
			nx--;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][1] = 1;
		}
		nx = x, ny = y;
		while(ny + 1 < N && !zabR[nx][ny] && (dis[nx][ny + 1] == -1 || dis[x][y] + 1 == dis[nx][ny + 1]) && !bio[nx][ny + 1][2]){
			ny++;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][2] = 1;
		}
		nx = x, ny = y;
		while(ny > 0 && !zabR[nx][ny - 1] && (dis[nx][ny - 1] == -1 || dis[x][y] + 1 == dis[nx][ny - 1]) && !bio[nx][ny - 1][3]){
			ny--;
			if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[x][y] + 1;
				Q.push({nx, ny}); 
			}
			bio[nx][ny][3] = 1;
		}
	}
	printf("%d\n", dis[t_x][t_y]);
	return 0;
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 149880 KB Output is correct
2 Correct 471 ms 150012 KB Output is correct
3 Correct 477 ms 149624 KB Output is correct
4 Correct 468 ms 149672 KB Output is correct
5 Correct 365 ms 141688 KB Output is correct
6 Correct 264 ms 135980 KB Output is correct
7 Correct 295 ms 144560 KB Output is correct
8 Correct 242 ms 142200 KB Output is correct
9 Correct 303 ms 140668 KB Output is correct
10 Correct 325 ms 144380 KB Output is correct
11 Correct 382 ms 143712 KB Output is correct
12 Correct 329 ms 143056 KB Output is correct
13 Correct 390 ms 144324 KB Output is correct
14 Correct 288 ms 135656 KB Output is correct
15 Correct 362 ms 147708 KB Output is correct
16 Correct 373 ms 137904 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 149880 KB Output is correct
2 Correct 471 ms 150012 KB Output is correct
3 Correct 477 ms 149624 KB Output is correct
4 Correct 468 ms 149672 KB Output is correct
5 Correct 365 ms 141688 KB Output is correct
6 Correct 264 ms 135980 KB Output is correct
7 Correct 295 ms 144560 KB Output is correct
8 Correct 242 ms 142200 KB Output is correct
9 Correct 303 ms 140668 KB Output is correct
10 Correct 325 ms 144380 KB Output is correct
11 Correct 382 ms 143712 KB Output is correct
12 Correct 329 ms 143056 KB Output is correct
13 Correct 390 ms 144324 KB Output is correct
14 Correct 288 ms 135656 KB Output is correct
15 Correct 362 ms 147708 KB Output is correct
16 Correct 373 ms 137904 KB Output is correct
17 Correct 226 ms 114576 KB Output is correct
18 Correct 245 ms 114796 KB Output is correct
19 Correct 186 ms 110320 KB Output is correct
20 Correct 228 ms 118056 KB Output is correct
21 Correct 204 ms 112996 KB Output is correct
22 Correct 203 ms 113372 KB Output is correct
23 Correct 198 ms 111832 KB Output is correct
24 Correct 184 ms 109980 KB Output is correct
25 Correct 203 ms 110800 KB Output is correct
26 Correct 191 ms 109156 KB Output is correct
27 Correct 354 ms 146684 KB Output is correct
28 Correct 362 ms 135300 KB Output is correct
29 Correct 375 ms 134772 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 149880 KB Output is correct
2 Correct 471 ms 150012 KB Output is correct
3 Correct 477 ms 149624 KB Output is correct
4 Correct 468 ms 149672 KB Output is correct
5 Correct 365 ms 141688 KB Output is correct
6 Correct 264 ms 135980 KB Output is correct
7 Correct 295 ms 144560 KB Output is correct
8 Correct 242 ms 142200 KB Output is correct
9 Correct 303 ms 140668 KB Output is correct
10 Correct 325 ms 144380 KB Output is correct
11 Correct 382 ms 143712 KB Output is correct
12 Correct 329 ms 143056 KB Output is correct
13 Correct 390 ms 144324 KB Output is correct
14 Correct 288 ms 135656 KB Output is correct
15 Correct 362 ms 147708 KB Output is correct
16 Correct 373 ms 137904 KB Output is correct
17 Correct 226 ms 114576 KB Output is correct
18 Correct 245 ms 114796 KB Output is correct
19 Correct 186 ms 110320 KB Output is correct
20 Correct 228 ms 118056 KB Output is correct
21 Correct 204 ms 112996 KB Output is correct
22 Correct 203 ms 113372 KB Output is correct
23 Correct 198 ms 111832 KB Output is correct
24 Correct 184 ms 109980 KB Output is correct
25 Correct 203 ms 110800 KB Output is correct
26 Correct 191 ms 109156 KB Output is correct
27 Correct 354 ms 146684 KB Output is correct
28 Correct 362 ms 135300 KB Output is correct
29 Correct 375 ms 134772 KB Output is correct
30 Execution timed out 12 ms 17152 KB Time limit exceeded (wall clock)
31 Halted 0 ms 0 KB -