Submission #41734

#	Time	Username	Problem	Language	Result	Execution time	Memory
41734		fest	Golf (JOI17_golf)	C++14	30 / 100	2850 ms	167412 KiB

golf

// 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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70