Submission #475565

#	Time	Username	Problem	Language	Result	Execution time	Memory
475565		youngyojun	Wall (CEOI14_wall)	C++17	100 / 100	426 ms	96440 KiB

wall

#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
void fg(vector<pii> G[], int a, int b, int c) { G[a].eb(b, c); G[b].eb(a, c); }
 
const bool debug = 0;
const int MAXH = 405;
const int MAXW = 405;
 
priority_queue<pli, vector<pli>, greater<pli>> PQ;
 
vector<pii> G[2200022];
 
ll dp[MAXH*2][MAXW*2]; int dpr[MAXH][MAXW];
 
bitset<MAXW> chk[MAXH], isB[MAXH], isC[MAXW];
 
int B[MAXH][MAXW], C[MAXH][MAXW];
int A[MAXH][MAXW];
 
int H, W;
 
int f(int y, int x) { return y<<11 | x; }
void updf(int y, int x, ll dst, int dr) {
	if(y < 0 || x < 0 || H < y || W < x) return;
	if(dp[y][x] <= dst) return;
 
	PQ.push(pli(dst, f(y, x)));
	dp[y][x] = dst;
	dpr[y][x] = dr;
}
 
int main() {
	ios::sync_with_stdio(false);
 
	cin >> H >> W;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) cin >> A[i][j];
	for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) cin >> B[i][j];
	for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) cin >> C[i][j];
	
	for(int i = 0; i <= H; i++) fill(dp[i], dp[i]+W+1, INFLL);
	dp[0][0] = 0; PQ.push(pli(0, 0));
	for(int y, x; !PQ.empty();) {
		ll dst; tie(dst, y) = PQ.top(); PQ.pop();
		x = y & ((1<<11)-1); y >>= 11;
		if(dp[y][x] < dst) continue;
 
		updf(y-1, x, dst + B[y][x], 0);
		updf(y+1, x, dst + B[y+1][x], 2);
		updf(y, x+1, dst + C[y][x+1], 1);
		updf(y, x-1, dst + C[y][x], 3);
	}
 
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j]) {
		for(int y = i-1, x = j-1; y || x;) {
			if(!dpr[y][x]) {
				y++;
				isB[y][x] = true;
			} else if(1 == dpr[y][x]) {
				isC[y][x] = true;
				x--;
			} else if(2 == dpr[y][x]) {
				isB[y][x] = true;
				y--;
			} else {
				x++;
				isC[y][x] = true;
			}
		}
	}
 
	if(debug) {
		for(int i = 1; i <= H; i++) {
			for(int j = 0; j <= W; j++)
				printf("%d ", int(isB[i][j]));
			puts("");
		}
		for(int i = 0; i <= H; i++) {
			for(int j = 1; j <= W; j++)
				printf("%d ", int(isC[i][j]));
			puts("");
		}
	}
 
	for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) {
		fg(G, f(i*2-1, j*2), f(i*2, j*2), B[i][j]);
		fg(G, f(i*2-1, j*2+1), f(i*2, j*2+1), B[i][j]);
	}
	for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) {
		fg(G, f(i*2, j*2-1), f(i*2, j*2), C[i][j]);
		fg(G, f(i*2+1, j*2-1), f(i*2+1, j*2), C[i][j]);
	}
 
	isB[0][0] = isC[0][0] = true;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j])
		isB[i][j-1] = isB[i][j] = isC[i-1][j] = isC[i][j] = true;
	for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++) {
		if(!isB[i][j]) fg(G, f(i*2, j*2), f(i*2, j*2+1), 0);
		if(!isC[i][j]) fg(G, f(i*2, j*2), f(i*2+1, j*2), 0);
		if(!isB[i+1][j]) fg(G, f(i*2+1, j*2), f(i*2+1, j*2+1), 0);
		if(!isC[i][j+1]) fg(G, f(i*2, j*2+1), f(i*2+1, j*2+1), 0);
	}
 
	for(int i = 0; i <= H*2+1; i++)
		fill(dp[i], dp[i]+W*2+2, INFLL);
	dp[0][1] = 0; PQ.push(pli(0, 1));
	for(int y, x; !PQ.empty();) {
		ll dst; tie(dst, y) = PQ.top(); PQ.pop();
		x = y & ((1<<11)-1); y >>= 11;
		if(dp[y][x] < dst) continue;
 
		vector<pii> &V = G[f(y, x)];
		for(auto &e : V) {
			int ny = e.first >> 11, nx = e.first & ((1<<11)-1);
			ll ndst = dst + e.second;
 
			if(dp[ny][nx] <= ndst) continue;
			dp[ny][nx] = ndst;
			PQ.push(pli(ndst, f(ny, nx)));
		}
	}
 
	cout << dp[1][0] << endl;
	return 0;
}

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