Submission #49878

#	Time	Username	Problem	Language	Result	Execution time	Memory
49878		aome	Wall (CEOI14_wall)	C++17	100 / 100	460 ms	22956 KiB

wall

#include <bits/stdc++.h>

using namespace std;

const int N = 405;
const long long INF = 1e18;

struct State {
	long long v;
	int x, y, d;

	State (long long v, int x, int y, int d) :
		v(v), x(x), y(y), d(d) {}

	bool operator < (const State& rhs) const {
		return v > rhs.v;
	}
};

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

int n, m;
int cost[4][N][N];
bool a[N][N];
bool vis[N][N];
bool mark[4][N][N];
long long dis[N][N];
long long f[4][N][N];

void dijkstra() {
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			dis[i][j] = INF;
		}
	}
	priority_queue<State> pq;
	pq.push(State(dis[1][1] = 0, 1, 1, 0));
	while (pq.size()) {
		long long v = pq.top().v;
		int x = pq.top().x, y = pq.top().y;
		pq.pop();
		if (v != dis[x][y]) continue;
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
			if (dis[nx][ny] > v + cost[i][x][y]) {
				dis[nx][ny] = v + cost[i][x][y];
				pq.push(State(dis[nx][ny], nx, ny, 0));
			}
		}
	}
}

void rec(int x, int y) {
	if (x == 1 && y == 1 || vis[x][y]) return;
	vis[x][y] = 1;
	for (int i = 0; i < 4; ++i) {
		int nx = x - dx[i], ny = y - dy[i];
		if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
		if (dis[nx][ny] + cost[i][nx][ny] == dis[x][y]) {
			mark[i ^ 1][x][y] = mark[i][nx][ny] = 1, rec(nx, ny); return;
		}
	}
}

void solve() {
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			for (int k = 0; k < 4; ++k) {
				f[k][i][j] = INF;
			}
		}
	}
	priority_queue<State> pq;
	pq.push(State(f[1][1][2] = cost[1][1][1], 1, 2, 1));
	while (pq.size()) {
		long long v = pq.top().v;
		int x = pq.top().x, y = pq.top().y, d = pq.top().d;
		pq.pop();
		if (v != f[d][x][y]) continue;

		if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
			if (f[0][x][y - 1] > v + cost[0][x][y]) {
				f[0][x][y - 1] = v + cost[0][x][y];
				pq.push(State(f[0][x][y - 1], x, y - 1, 0));
			}
		}

		if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
			if (f[1][x][y + 1] > v + cost[1][x][y]) {
				f[1][x][y + 1] = v + cost[1][x][y];
				pq.push(State(f[1][x][y + 1], x, y + 1, 1));
			}
		}

		if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
			if (f[2][x - 1][y] > v + cost[2][x][y]) {
				f[2][x - 1][y] = v + cost[2][x][y];
				pq.push(State(f[2][x - 1][y], x - 1, y, 2));
			}
		}

		if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
			if (f[3][x + 1][y] > v + cost[3][x][y]) {
				f[3][x + 1][y] = v + cost[3][x][y];
				pq.push(State(f[3][x + 1][y], x + 1, y, 3));
			}
		}

		// if (d == 0) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 1) continue;
		// 		if (i.d == 0 && mark[3][x][y]) continue;
		// 		if (i.d == 2 && (mark[0][x][y] || mark[3][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 1) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 0) continue;
		// 		if (i.d == 1 && mark[2][x][y]) continue;
		// 		if (i.d == 3 && (mark[1][x][y] || mark[2][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 2) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 3) continue;
		// 		if (i.d == 2 && mark[0][x][y]) continue;
		// 		if (i.d == 1 && (mark[0][x][y] || mark[2][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 3) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 2) continue;
		// 		if (i.d == 3 && mark[1][x][y]) continue;
		// 		if (i.d == 0 && (mark[1][x][y] || mark[3][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			if (a[i][j]) {
				mark[0][i][j + 1] = mark[0][i + 1][j + 1] = 1;
				mark[1][i][j] = mark[1][i + 1][j] = 1;
				mark[2][i + 1][j] = mark[2][i + 1][j + 1] = 1;
				mark[3][i][j] = mark[3][i][j + 1] = 1;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			int w; cin >> w;
			cost[3][i][j] = cost[2][i + 1][j] = w;
		}
	} 
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m; ++j) {
			int w; cin >> w;
			cost[1][i][j] = cost[0][i][j + 1] = w;
		}
	}
	dijkstra();
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j]) rec(i, j);
		}
	}
	// for (int i = 1; i <= n + 1; ++i) {
	// 	for (int j = 1; j <= m + 1; ++j) {
	// 		for (int k = 1; k < 4; k += 2) {
	// 			if (mark[k][i][j]) {
	// 				cout << i << ' ' << j << ' ' << k << '\n';
	// 			}
	// 		}
	// 	}
	// }
	solve();
	cout << f[2][1][1];
}

Compilation message (stderr)

wall.cpp: In function 'void rec(int, int)':
wall.cpp:56:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  if (x == 1 && y == 1 || vis[x][y]) return;
      ~~~~~~~^~~~~~~~~
wall.cpp: In function 'void solve()':
wall.cpp:83:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:83:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:90:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
                    ~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:90:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:97:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
                                                                  ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40