답안 #26560 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26560	2017-07-03T05:52:42 Z	gs14004	Golf (JOI17_golf)	C++14	30 / 100	1242 ms	114752 KB

golf

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #26560

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 70.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 70.0