Submission #253981

#	Time	Username	Problem	Language	Result	Execution time	Memory
253981		TadijaSebez	Wall (CEOI14_wall)	C++11	100 / 100	406 ms	25308 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ban(x,y) ban[(x)-(go[(x)][(y)]==0)][(y)-(go[(x)][(y)]==1)][go[(x)][(y)]&1]
const int N=405;
const ll inf=9e18;
ll dist[N][N],ans[N][N][4];
int w[N][N][2],has[N][N],go[N][N],ban[N][N][2];
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}},blk[4][2]={{0,2},{0,1},{1,3},{2,3}};
int main(){
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%i",&has[i][j]);
	for(int i=0;i<n;i++)for(int j=0;j<=m;j++)scanf("%i",&w[i][j][0]);
	for(int i=0;i<=n;i++)for(int j=0;j<m;j++)scanf("%i",&w[i][j][1]);
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dist[i][j]=inf;
	dist[0][0]=0;
	priority_queue<array<ll,3>> pq;
	pq.push({0,0,0});
	while(pq.size()){
		int x=pq.top()[1],y=pq.top()[2];
		ll d=-pq.top()[0];
		pq.pop();
		if(dist[x][y]!=d)continue;
		for(int i=0;i<4;i++){
			int nx=x+mv[i][0],ny=y+mv[i][1];
			if(nx<0||nx>n||ny<0||ny>m)continue;
			ll now=d+w[nx-(i==0)][ny-(i==1)][i&1];
			if(dist[nx][ny]>now){
				dist[nx][ny]=now;
				go[nx][ny]=i;
				pq.push({-now,nx,ny});
			}
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(has[i][j]){
		int x=i,y=j;
		while(x||y){
			if(ban(x,y))
				break;
			ban(x,y)=1;
			int tmp=go[x][y];
			x-=mv[tmp][0];
			y-=mv[tmp][1];
		}
		ban[i][j][0]=ban[i][j+1][0]=ban[i][j][1]=ban[i+1][j][1]=1;
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<4;k++)ans[i][j][k]=inf;
	ans[0][0][1]=0;
	priority_queue<array<ll,4>> pq2;
	pq2.push({0,0,0,1});
	while(pq2.size()){
		int x=pq2.top()[1],y=pq2.top()[2],k=pq2.top()[3];
		ll d=-pq2.top()[0];
		pq2.pop();
		if(d!=ans[x][y][k])continue;
		if(x||y){
			if(x-1+k%2<0||x-1+k%2>=n||!ban[x-1+k%2][y][0]){
				if(ans[x][y][k^2]>d){
					ans[x][y][k^2]=d;
					pq2.push({-d,x,y,k^2});
				}
			}
			if(y-1+k/2<0||y-1+k/2>=m||!ban[x][y-1+k/2][1]){
				if(ans[x][y][k^1]>d){
					ans[x][y][k^1]=d;
					pq2.push({-d,x,y,k^1});
				}
			}
		}
		for(int i=0;i<4;i++){
			int nx=x+mv[i][0],ny=y+mv[i][1],nk=k^(i%2+1);
			if(nx<0||nx>n||ny<0||ny>m||k==blk[i][0]||k==blk[i][1])continue;
			ll now=d+w[nx-(i==0)][ny-(i==1)][i&1];
			if(ans[nx][ny][nk]>now){
				ans[nx][ny][nk]=now;
				pq2.push({-now,nx,ny,nk});
			}
		}
	}
	printf("%lld\n",ans[0][0][2]);
	return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int main()':
wall.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
wall.cpp:13:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%i",&has[i][j]);
                                          ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:14:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++)for(int j=0;j<=m;j++)scanf("%i",&w[i][j][0]);
                                           ~~~~~^~~~~~~~~~~~~~~~~~
wall.cpp:15:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<=n;i++)for(int j=0;j<m;j++)scanf("%i",&w[i][j][1]);
                                           ~~~~~^~~~~~~~~~~~~~~~~~

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