oj.uz

Submission #475565

# Submission time Handle Problem Language Result Execution time Memory
475565 2021-09-23T02:56:02 Z youngyojun Wall (CEOI14_wall) C++17
100 / 100
 426 ms 96440 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52172 KB Output is correct
2 Correct 25 ms 52136 KB Output is correct
3 Correct 25 ms 52192 KB Output is correct
4 Correct 28 ms 52132 KB Output is correct
5 Correct 26 ms 52112 KB Output is correct
6 Correct 27 ms 52664 KB Output is correct
7 Correct 26 ms 52576 KB Output is correct
8 Correct 29 ms 52684 KB Output is correct
9 Correct 27 ms 52512 KB Output is correct
10 Correct 29 ms 52632 KB Output is correct
11 Correct 27 ms 52760 KB Output is correct
12 Correct 28 ms 52892 KB Output is correct
13 Correct 28 ms 53020 KB Output is correct
14 Correct 36 ms 52968 KB Output is correct
15 Correct 35 ms 52812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 52888 KB Output is correct
2 Correct 32 ms 52980 KB Output is correct
3 Correct 30 ms 52916 KB Output is correct
4 Correct 30 ms 52940 KB Output is correct
5 Correct 31 ms 52976 KB Output is correct
6 Correct 28 ms 53004 KB Output is correct
7 Correct 28 ms 53016 KB Output is correct
8 Correct 28 ms 52956 KB Output is correct
9 Correct 32 ms 53012 KB Output is correct
10 Correct 29 ms 53068 KB Output is correct
11 Correct 28 ms 52928 KB Output is correct
12 Correct 31 ms 52932 KB Output is correct
13 Correct 35 ms 52912 KB Output is correct
14 Correct 31 ms 52976 KB Output is correct
15 Correct 28 ms 52996 KB Output is correct
16 Correct 32 ms 53028 KB Output is correct
17 Correct 30 ms 52912 KB Output is correct
18 Correct 31 ms 52940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 63900 KB Output is correct
2 Correct 100 ms 62332 KB Output is correct
3 Correct 92 ms 63100 KB Output is correct
4 Correct 100 ms 63456 KB Output is correct
5 Correct 195 ms 75164 KB Output is correct
6 Correct 127 ms 63948 KB Output is correct
7 Correct 279 ms 77352 KB Output is correct
8 Correct 225 ms 76356 KB Output is correct
9 Correct 195 ms 76612 KB Output is correct
10 Correct 245 ms 77796 KB Output is correct
11 Correct 320 ms 79164 KB Output is correct
12 Correct 93 ms 63724 KB Output is correct
13 Correct 218 ms 75692 KB Output is correct
14 Correct 315 ms 89028 KB Output is correct
15 Correct 357 ms 91076 KB Output is correct
16 Correct 426 ms 92264 KB Output is correct
17 Correct 420 ms 94272 KB Output is correct
18 Correct 418 ms 96440 KB Output is correct
19 Correct 395 ms 92384 KB Output is correct
20 Correct 348 ms 91528 KB Output is correct