Submission #26211

#	Time	Username	Problem	Language	Result	Execution time	Memory
26211		samir_droubi	Portals (BOI14_portals)	C++14	70 / 100	1000 ms	117328 KiB

portals

#pragma optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int mxn=1005;
int n,m;
char g[mxn][mxn];
int id[mxn][mxn];
vector<pair<int,int> >adj[mxn*mxn];

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool check(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='#';
}

int wall[mxn*mxn];
queue<int>q;
void bfs()
{
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		for(int i=0;i<adj[v].size();++i)
		{
			int u=adj[v][i].first;
			if(wall[u]>wall[v]+1)
			{
				wall[u]=wall[v]+1;
				q.push(u);
			}
		}
	}
}


int dist[mxn*mxn];
priority_queue<pair<int,int >,vector<pair<int,int> > ,greater<pair<int,int> > >pq;
void dijkstra(int s)
{
	dist[s]=0;
	pq.push({0,s});
	while(!pq.empty())
	{
		pair<int,int > p=pq.top();
		pq.pop();
		int ds=p.first;
		int v=p.second;
		for(int i=0;i<adj[v].size();++i)
		{
			int u=adj[v][i].first;
			int w=adj[v][i].second;
			if(dist[u]>ds+w)
			{
				dist[u]=ds+w;
				pq.push({ds+w,u});
			}
		}		
	}
}

void clear()
{
	for(int i=0;i<mxn*mxn;++i)
	{
		wall[i]=(1e9);
		dist[i]=(1e9);
	}
}
void up(int i,int j)
{
	int x=i;
	while(x>=1&&g[x][j]!='#')
	{
		adj[id[x][j]].push_back({id[i][j],wall[id[x][j]]});
		--x;
	}
}
void down(int i,int j)
{
	int x=i;
	while(x<=n&&g[x][j]!='#')
	{
		adj[id[x][j]].push_back({id[i][j],wall[id[x][j]]});
		++x;
	}
}
void left(int i,int j)
{
	int y=j;
	while(y>=1&&g[i][y]!='#')
	{
		adj[id[i][y]].push_back({id[i][j],wall[id[i][y]]});
		--y;
	}
}
void right(int i,int j)
{
	int y=j;
	while(y<=m&&g[i][y]!='#')
	{
		adj[id[i][y]].push_back({id[i][j],wall[id[i][y]]});
		++y;
	}
}
int main()
{
	//int start_s=clock();
	clear();
	int st,en;

	scanf("%d%d",&n,&m);
	int cur=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			id[i][j]=++cur;

	for(int i=1;i<=n;++i)
	{
		scanf("%s",&g[i]);
		g[i][m+1]='\0';
		for(int j=m;j>=1;--j)
		{
			g[i][j]=g[i][j-1];
			if(g[i][j]=='S')
				st=id[i][j];
			if(g[i][j]=='C')
				en=id[i][j];
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			bool ok=false;
			for(int k=0;k<4;++k)
			{
				int x=i+dx[k];
				int y=j+dy[k];
				if(!check(x,y))ok=true;
				else adj[id[i][j]].push_back({id[x][y],1});
			}
			if(ok)
			{
				wall[id[i][j]]=1;
				q.push(id[i][j]);
			}
		}	

	bfs();

	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			if(g[i][j]!='#')continue;
			right(i,j+1);
			left(i,j-1);
			up(i-1,j);
			down(i+1,j);
		}
	for(int i=1;i<=n;++i)
	{
		right(i,1);
		left(i,n);
	}
	for(int j=1;j<=m;++j)
	{
		down(1,j);
		up(m,j);
	}

	dijkstra(st);
	printf("%d\n",dist[en]);
	//int stop_s=clock();
	//cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
	return 0;
}

Compilation message (stderr)

portals.cpp:1:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("O3")
 ^
portals.cpp: In function 'void bfs()':
portals.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[v].size();++i)
                ^
portals.cpp: In function 'void dijkstra(int)':
portals.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[v].size();++i)
                ^
portals.cpp: In function 'int main()':
portals.cpp:120:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1005]' [-Wformat=]
   scanf("%s",&g[i]);
                   ^
portals.cpp:112:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
portals.cpp:120:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",&g[i]);
                    ^
portals.cpp:172:8: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
  printf("%d\n",dist[en]);
        ^
portals.cpp:171:14: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dijkstra(st);
              ^

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30