oj.uz

Submission #26560

# Submission time Handle Problem Language Result Execution time Memory
26560 2017-07-03T05:52:42 Z gs14004 Golf (JOI17_golf) C++14
30 / 100
 1242 ms 114752 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16896 KB Output is correct
3 Correct 15 ms 16896 KB Output is correct
4 Correct 18 ms 20348 KB Output is correct
5 Correct 176 ms 37036 KB Output is correct
6 Correct 119 ms 34020 KB Output is correct
7 Correct 197 ms 38300 KB Output is correct
8 Correct 169 ms 38468 KB Output is correct
9 Correct 214 ms 33212 KB Output is correct
10 Correct 107 ms 34660 KB Output is correct
11 Correct 117 ms 38756 KB Output is correct
12 Correct 80 ms 34604 KB Output is correct
13 Correct 207 ms 38176 KB Output is correct
14 Correct 186 ms 38620 KB Output is correct
15 Correct 119 ms 23648 KB Output is correct
16 Correct 424 ms 30324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16896 KB Output is correct
3 Correct 15 ms 16896 KB Output is correct
4 Correct 18 ms 20348 KB Output is correct
5 Correct 176 ms 37036 KB Output is correct
6 Correct 119 ms 34020 KB Output is correct
7 Correct 197 ms 38300 KB Output is correct
8 Correct 169 ms 38468 KB Output is correct
9 Correct 214 ms 33212 KB Output is correct
10 Correct 107 ms 34660 KB Output is correct
11 Correct 117 ms 38756 KB Output is correct
12 Correct 80 ms 34604 KB Output is correct
13 Correct 207 ms 38176 KB Output is correct
14 Correct 186 ms 38620 KB Output is correct
15 Correct 119 ms 23648 KB Output is correct
16 Correct 424 ms 30324 KB Output is correct
17 Correct 1111 ms 114080 KB Output is correct
18 Correct 958 ms 114316 KB Output is correct
19 Correct 538 ms 81640 KB Output is correct
20 Correct 1046 ms 81596 KB Output is correct
21 Correct 993 ms 114752 KB Output is correct
22 Correct 566 ms 81996 KB Output is correct
23 Correct 480 ms 81896 KB Output is correct
24 Correct 1242 ms 82020 KB Output is correct
25 Correct 230 ms 65488 KB Output is correct
26 Correct 856 ms 81944 KB Output is correct
27 Correct 136 ms 24960 KB Output is correct
28 Correct 522 ms 31608 KB Output is correct
29 Correct 494 ms 31868 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16896 KB Output is correct
3 Correct 15 ms 16896 KB Output is correct
4 Correct 18 ms 20348 KB Output is correct
5 Correct 176 ms 37036 KB Output is correct
6 Correct 119 ms 34020 KB Output is correct
7 Correct 197 ms 38300 KB Output is correct
8 Correct 169 ms 38468 KB Output is correct
9 Correct 214 ms 33212 KB Output is correct
10 Correct 107 ms 34660 KB Output is correct
11 Correct 117 ms 38756 KB Output is correct
12 Correct 80 ms 34604 KB Output is correct
13 Correct 207 ms 38176 KB Output is correct
14 Correct 186 ms 38620 KB Output is correct
15 Correct 119 ms 23648 KB Output is correct
16 Correct 424 ms 30324 KB Output is correct
17 Correct 1111 ms 114080 KB Output is correct
18 Correct 958 ms 114316 KB Output is correct
19 Correct 538 ms 81640 KB Output is correct
20 Correct 1046 ms 81596 KB Output is correct
21 Correct 993 ms 114752 KB Output is correct
22 Correct 566 ms 81996 KB Output is correct
23 Correct 480 ms 81896 KB Output is correct
24 Correct 1242 ms 82020 KB Output is correct
25 Correct 230 ms 65488 KB Output is correct
26 Correct 856 ms 81944 KB Output is correct
27 Correct 136 ms 24960 KB Output is correct
28 Correct 522 ms 31608 KB Output is correct
29 Correct 494 ms 31868 KB Output is correct
30 Incorrect 5 ms 384 KB Output isn't correct
31 Halted 0 ms 0 KB -