oj.uz

Submission #41734

# Submission time Handle Problem Language Result Execution time Memory
41734 2018-02-21T05:57:29 Z fest Golf (JOI17_golf) C++14
30 / 100
 2850 ms 167412 KB 
// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 1111, inf = 1e9 + 1, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int x1[N], x2[N], y1[N], y2[N], dp[N + N][N + N][4];

bool no[N + N][N + N][4];

int pos(const vector<int> &all, int x) {
	return lower_bound(All(all), x) - all.begin();
}

int main() {
  
	vector<int> all_x, all_y;
	int st[2], fi[2];
	cin >> st[0] >> st[1] >> fi[0] >> fi[1];
	all_x.pb(0);
	all_y.pb(0);
	all_x.pb(st[0]);
	all_x.pb(fi[0]);
	all_y.pb(st[1]);
	all_y.pb(fi[1]);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d %d", x1 + i, x2 + i, y1 + i, y2 + i);
		all_x.pb(x1[i]), all_x.pb(x2[i]);
		all_y.pb(y1[i]), all_y.pb(y2[i]);
	}
	sort(All(all_x)), all_x.resize(unique(All(all_x)) - all_x.begin());
	sort(All(all_y)), all_y.resize(unique(All(all_y)) - all_y.begin());
	st[0] = pos(all_x, st[0]);
	st[1] = pos(all_y, st[1]);
	fi[0] = pos(all_x, fi[0]);
	fi[1] = pos(all_y, fi[1]);
	for (int i = 1; i <= n; i++) {
		x1[i] = pos(all_x, x1[i]);
		x2[i] = pos(all_x, x2[i]);
		y1[i] = pos(all_y, y1[i]);
		y2[i] = pos(all_y, y2[i]);
		for (int x = x1[i] + 1; x < x2[i]; x++) no[x][y1[i]][2] = no[x][y2[i]][3] = 1;
		for (int y = y1[i] + 1; y < y2[i]; y++) no[x1[i]][y][0] = no[x2[i]][y][1] = 1;
	}
	int mx = SZ(all_x), my = SZ(all_y);
	for (int i = 0; i < mx; i++) for (int j = 0; j < my; j++) for (int dir = 0; dir < 4; dir++) dp[i][j][dir] = inf;
	set<pair<int, pair<int, pair<int, int> > > > s;
	for (int dir = 0; dir < 4; dir++) dp[st[0]][st[1]][dir] = 1, s.insert({1, {st[0], {st[1], dir}}});
	while (!s.empty()) {
		int x = s.begin() -> S.F;
		int y = s.begin() -> S.S.F;
		int dir = s.begin() -> S.S.S;
		s.erase(s.begin());
		for (int dir2 = 0; dir2 < 4; dir2++) {
			if (no[x][y][dir2]) continue;
			int ux = x + dx[dir2], uy = y + dy[dir2];
			if (ux == 0 || uy == 0 || ux >= mx || uy >= my) continue;
			if (dp[ux][uy][dir2] > dp[x][y][dir] + (dir != dir2)) {
				s.erase({dp[ux][uy][dir2], {ux, {uy, dir2}}});
				dp[ux][uy][dir2] = dp[x][y][dir] + (dir != dir2);
				s.insert({dp[ux][uy][dir2], {ux, {uy, dir2}}});
			}
		}
		for (int dir2 = 0; dir2 < 4; dir2++) {
			if (no[x][y][dir2]) continue;
			if (dp[x][y][dir2] > dp[x][y][dir] + (dir != dir2)) {
				s.erase({dp[x][y][dir2], {x, {y, dir2}}});
				dp[x][y][dir2] = dp[x][y][dir] + (dir != dir2);
				s.insert({dp[x][y][dir2], {x, {y, dir2}}});
			}	
		}
	}
	int ans = inf;
	for (int dir = 0; dir < 4; dir++) ans = min(ans, dp[fi[0]][fi[1]][dir]);
	cout << ans;
	return 0;	
}

Compilation message

golf.cpp: In function 'void FREOPEN()':
golf.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", x1 + i, x2 + i, y1 + i, y2 + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 26 ms 3584 KB Output is correct
5 Correct 386 ms 32248 KB Output is correct
6 Correct 356 ms 30432 KB Output is correct
7 Correct 317 ms 28000 KB Output is correct
8 Correct 355 ms 29940 KB Output is correct
9 Correct 352 ms 27516 KB Output is correct
10 Correct 373 ms 30840 KB Output is correct
11 Correct 412 ms 31736 KB Output is correct
12 Correct 336 ms 26864 KB Output is correct
13 Correct 314 ms 27492 KB Output is correct
14 Correct 405 ms 32852 KB Output is correct
15 Correct 179 ms 7312 KB Output is correct
16 Correct 763 ms 20464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 26 ms 3584 KB Output is correct
5 Correct 386 ms 32248 KB Output is correct
6 Correct 356 ms 30432 KB Output is correct
7 Correct 317 ms 28000 KB Output is correct
8 Correct 355 ms 29940 KB Output is correct
9 Correct 352 ms 27516 KB Output is correct
10 Correct 373 ms 30840 KB Output is correct
11 Correct 412 ms 31736 KB Output is correct
12 Correct 336 ms 26864 KB Output is correct
13 Correct 314 ms 27492 KB Output is correct
14 Correct 405 ms 32852 KB Output is correct
15 Correct 179 ms 7312 KB Output is correct
16 Correct 763 ms 20464 KB Output is correct
17 Correct 2850 ms 162952 KB Output is correct
18 Correct 2619 ms 157236 KB Output is correct
19 Correct 2376 ms 133828 KB Output is correct
20 Correct 2491 ms 150512 KB Output is correct
21 Correct 2728 ms 167412 KB Output is correct
22 Correct 2557 ms 155000 KB Output is correct
23 Correct 2488 ms 137212 KB Output is correct
24 Correct 2350 ms 132076 KB Output is correct
25 Correct 2450 ms 146528 KB Output is correct
26 Correct 2430 ms 130328 KB Output is correct
27 Correct 289 ms 9472 KB Output is correct
28 Correct 903 ms 23928 KB Output is correct
29 Correct 945 ms 24376 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 26 ms 3584 KB Output is correct
5 Correct 386 ms 32248 KB Output is correct
6 Correct 356 ms 30432 KB Output is correct
7 Correct 317 ms 28000 KB Output is correct
8 Correct 355 ms 29940 KB Output is correct
9 Correct 352 ms 27516 KB Output is correct
10 Correct 373 ms 30840 KB Output is correct
11 Correct 412 ms 31736 KB Output is correct
12 Correct 336 ms 26864 KB Output is correct
13 Correct 314 ms 27492 KB Output is correct
14 Correct 405 ms 32852 KB Output is correct
15 Correct 179 ms 7312 KB Output is correct
16 Correct 763 ms 20464 KB Output is correct
17 Correct 2850 ms 162952 KB Output is correct
18 Correct 2619 ms 157236 KB Output is correct
19 Correct 2376 ms 133828 KB Output is correct
20 Correct 2491 ms 150512 KB Output is correct
21 Correct 2728 ms 167412 KB Output is correct
22 Correct 2557 ms 155000 KB Output is correct
23 Correct 2488 ms 137212 KB Output is correct
24 Correct 2350 ms 132076 KB Output is correct
25 Correct 2450 ms 146528 KB Output is correct
26 Correct 2430 ms 130328 KB Output is correct
27 Correct 289 ms 9472 KB Output is correct
28 Correct 903 ms 23928 KB Output is correct
29 Correct 945 ms 24376 KB Output is correct
30 Execution timed out 8 ms 512 KB Time limit exceeded (wall clock)
31 Halted 0 ms 0 KB -