oj.uz

Submission #475566

# Submission time Handle Problem Language Result Execution time Memory
475566 2021-09-23T02:57:15 Z youngyojun Wall (CEOI14_wall) C++17
100 / 100
 417 ms 94012 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); }

priority_queue<pli, vector<pli>, greater<pli>> PQ;
 
vector<pii> G[2200022];
 
ll dp[405*2][405*2]; int dpr[405][405];
 
bitset<405> chk[405], isB[405], isC[405];
 
int B[405][405], C[405][405];
int A[405][405];
 
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;
			}
		}
	}
 
	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 52068 KB Output is correct
2 Correct 27 ms 52132 KB Output is correct
3 Correct 28 ms 52140 KB Output is correct
4 Correct 27 ms 52184 KB Output is correct
5 Correct 33 ms 52172 KB Output is correct
6 Correct 26 ms 52684 KB Output is correct
7 Correct 27 ms 52632 KB Output is correct
8 Correct 28 ms 52692 KB Output is correct
9 Correct 28 ms 52560 KB Output is correct
10 Correct 26 ms 52696 KB Output is correct
11 Correct 27 ms 52756 KB Output is correct
12 Correct 30 ms 52852 KB Output is correct
13 Correct 28 ms 52976 KB Output is correct
14 Correct 29 ms 52904 KB Output is correct
15 Correct 27 ms 52808 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52940 KB Output is correct
2 Correct 30 ms 52956 KB Output is correct
3 Correct 30 ms 52968 KB Output is correct
4 Correct 29 ms 53004 KB Output is correct
5 Correct 30 ms 52984 KB Output is correct
6 Correct 28 ms 53012 KB Output is correct
7 Correct 28 ms 53008 KB Output is correct
8 Correct 30 ms 52888 KB Output is correct
9 Correct 28 ms 52940 KB Output is correct
10 Correct 33 ms 52992 KB Output is correct
11 Correct 30 ms 52888 KB Output is correct
12 Correct 36 ms 52940 KB Output is correct
13 Correct 30 ms 53016 KB Output is correct
14 Correct 28 ms 52940 KB Output is correct
15 Correct 32 ms 52900 KB Output is correct
16 Correct 31 ms 52964 KB Output is correct
17 Correct 30 ms 53016 KB Output is correct
18 Correct 27 ms 52940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 63476 KB Output is correct
2 Correct 94 ms 61988 KB Output is correct
3 Correct 90 ms 62700 KB Output is correct
4 Correct 123 ms 62800 KB Output is correct
5 Correct 209 ms 74080 KB Output is correct
6 Correct 108 ms 63428 KB Output is correct
7 Correct 234 ms 76484 KB Output is correct
8 Correct 222 ms 75652 KB Output is correct
9 Correct 189 ms 75308 KB Output is correct
10 Correct 229 ms 76356 KB Output is correct
11 Correct 260 ms 77668 KB Output is correct
12 Correct 85 ms 63300 KB Output is correct
13 Correct 215 ms 74664 KB Output is correct
14 Correct 353 ms 87744 KB Output is correct
15 Correct 367 ms 89984 KB Output is correct
16 Correct 342 ms 90188 KB Output is correct
17 Correct 417 ms 91968 KB Output is correct
18 Correct 416 ms 94012 KB Output is correct
19 Correct 406 ms 90720 KB Output is correct
20 Correct 334 ms 89664 KB Output is correct