oj.uz

Submission #77313

# Submission time Handle Problem Language Result Execution time Memory
77313 2018-09-25T12:31:58 Z tmwilliamlin168 Wall (CEOI14_wall) C++14
100 / 100
 425 ms 38380 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=400, nb[4][2]={{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, f[4][2]={{1, 3}, {2, 3}, {0, 2}, {0, 1}};
int n, m, e[mxN+1][mxN+1][2], p[mxN+1][mxN+1], a[mxN][mxN], b[mxN+1][mxN+1][2];;
ll d[mxN+1][mxN+1][4];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;

void dijkstra(bool c) {
	memset(d, 0x3f, sizeof(d));
	d[0][0][1]=0;
	pq.push({0, 0, 0, 1});
	while(!pq.empty()) {
		array<ll, 4> u=pq.top();
		pq.pop();
		int i=u[1], j=u[2], k=u[3];
//		cout << u[0] << " " << i << " " << j << " " << k << endl;
//		if(i==0&&j==0&&k==2)
//			exit(0);
		if(d[i][j][k]<u[0])
			continue;
		if(c&&(i||j)) {
//			if(i==2&&j==1&&k==1)
//				cout << (b[i-1+k%2][j][0]) << endl;
			if((i<1-k%2||!b[i-1+k%2][j][0])&&d[i][j][k^2]>u[0]) {
				d[i][j][k^2]=u[0];
				pq.push({u[0], i, j, k^2});
			}
			if((j<1-k/2||!b[i][j-1+k/2][1])&&d[i][j][k^1]>u[0]) {
				d[i][j][k^1]=u[0];
				pq.push({u[0], i, j, k^1});
			}
		}
		for(int l=0; l<4; ++l) {
			int ni=i+nb[l][0], nj=j+nb[l][1];
			if(c&&f[l][0]!=k&&f[l][1]!=k||ni<0||ni>n||nj<0||nj>m)
				continue;
			int nk=k^(c?l%2+1:0), ne=e[i-(l==2)][j-(l==3)][l&1];
			if(d[ni][nj][nk]>u[0]+ne) {
				d[ni][nj][nk]=u[0]+ne;
				pq.push({u[0]+ne, ni, nj, nk});
				p[ni][nj]=l;
			}
		}
	}
	if(c)
		cout << d[0][0][2];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			cin >> a[i][j];
	for(int k=0; k<2; ++k)
		for(int i=0; i<n+k; ++i)
			for(int j=0; j<m+!k; ++j)
				cin >> e[i][j][k];
	dijkstra(0);
//	cout << "hi1" << endl;
	for(int i1=0; i1<n; ++i1) {
		for(int j1=0; j1<m; ++j1) {
			if(!a[i1][j1])
				continue;
			int i=i1, j=j1;
//			cout << "in " << i << " " << j << endl;
			while(i||j) {
				int cp=p[i][j], &cb=b[i-(cp==0)][j-(cp==1)][cp&1];
//				cout << i << " " << j << " " << cp << endl;
				if(cb)
					break;
				cb=1;
				i-=nb[cp][0];
				j-=nb[cp][1];
			}
			b[i1][j1][0]=b[i1][j1][1]=b[i1][j1+1][0]=b[i1+1][j1][1]=1;
		}
	}
//	cout << "hi2" << endl;
	dijkstra(1);
}

Compilation message

wall.cpp: In function 'void dijkstra(bool)':
wall.cpp:38:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(c&&f[l][0]!=k&&f[l][1]!=k||ni<0||ni>n||nj<0||nj>m)
       ~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5496 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 7 ms 5736 KB Output is correct
4 Correct 7 ms 5736 KB Output is correct
5 Correct 7 ms 5748 KB Output is correct
6 Correct 8 ms 6008 KB Output is correct
7 Correct 8 ms 6032 KB Output is correct
8 Correct 8 ms 6032 KB Output is correct
9 Correct 9 ms 6048 KB Output is correct
10 Correct 8 ms 6236 KB Output is correct
11 Correct 9 ms 6248 KB Output is correct
12 Correct 9 ms 6248 KB Output is correct
13 Correct 9 ms 6384 KB Output is correct
14 Correct 10 ms 6384 KB Output is correct
15 Correct 11 ms 6384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6384 KB Output is correct
2 Correct 10 ms 6476 KB Output is correct
3 Correct 9 ms 6476 KB Output is correct
4 Correct 10 ms 6516 KB Output is correct
5 Correct 10 ms 6536 KB Output is correct
6 Correct 12 ms 6536 KB Output is correct
7 Correct 10 ms 6576 KB Output is correct
8 Correct 9 ms 6576 KB Output is correct
9 Correct 9 ms 6576 KB Output is correct
10 Correct 10 ms 6820 KB Output is correct
11 Correct 10 ms 6820 KB Output is correct
12 Correct 14 ms 6820 KB Output is correct
13 Correct 10 ms 6820 KB Output is correct
14 Correct 9 ms 6820 KB Output is correct
15 Correct 9 ms 6820 KB Output is correct
16 Correct 13 ms 6820 KB Output is correct
17 Correct 10 ms 6820 KB Output is correct
18 Correct 9 ms 6820 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9112 KB Output is correct
2 Correct 76 ms 9112 KB Output is correct
3 Correct 55 ms 9112 KB Output is correct
4 Correct 94 ms 11920 KB Output is correct
5 Correct 80 ms 12048 KB Output is correct
6 Correct 74 ms 12048 KB Output is correct
7 Correct 215 ms 14256 KB Output is correct
8 Correct 191 ms 14256 KB Output is correct
9 Correct 136 ms 14720 KB Output is correct
10 Correct 184 ms 18744 KB Output is correct
11 Correct 224 ms 22280 KB Output is correct
12 Correct 43 ms 22280 KB Output is correct
13 Correct 160 ms 22280 KB Output is correct
14 Correct 234 ms 22788 KB Output is correct
15 Correct 292 ms 23192 KB Output is correct
16 Correct 263 ms 25160 KB Output is correct
17 Correct 389 ms 31852 KB Output is correct
18 Correct 425 ms 38380 KB Output is correct
19 Correct 359 ms 38380 KB Output is correct
20 Correct 289 ms 38380 KB Output is correct