Submission #159159

#	Time	Username	Problem	Language	Result	Execution time	Memory
159159		TadijaSebez	Dangerous Skating (JOI16_skating)	C++11	100 / 100	1402 ms	209908 KiB

skating

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=1e9+7;
const int N=1050;
const int H=N*N*4;
int n,m;
int ID(int x, int y){ return (x-1)*m+y;}
vector<pair<int,int>> E[H];
int dist[H];
bool was[H];
char base[N][N];
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1,k=1;j<=m;j++)
		{
			if(base[i][j]=='#') k=j+1;
			else E[ID(i,j)].pb({ID(i,k),1});
		}
		for(int j=m,k=m;j>=1;j--)
		{
			if(base[i][j]=='#') k=j-1;
			else E[ID(i,j)].pb({ID(i,k),1});
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1,k=1;j<=n;j++)
		{
			if(base[j][i]=='#') k=j+1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
		for(int j=n,k=n;j>=1;j--)
		{
			if(base[j][i]=='#') k=j-1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.')
	{
		if(base[i][j-1]=='.') E[ID(i,j)].pb({ID(i,j-1),2});
		if(base[i][j+1]=='.') E[ID(i,j)].pb({ID(i,j+1),2});
		if(base[i-1][j]=='.') E[ID(i,j)].pb({ID(i-1,j),2});
		if(base[i+1][j]=='.') E[ID(i,j)].pb({ID(i+1,j),2});
	}
	int x,y,a,b;
	scanf("%i %i %i %i",&x,&y,&a,&b);
	if(x==a && y==b) return 0*printf("0\n");
	for(int i=0;i<H;i++) dist[i]=inf;
	priority_queue<pair<int,int>> pq;
	pq.push({0,ID(x,y)});
	dist[ID(x,y)]=0;
	while(pq.size())
	{
		int u,d;tie(d,u)=pq.top();d=-d;pq.pop();
		if(d!=dist[u]) continue;
		for(auto e:E[u])
		{
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w)
			{
				dist[v]=dist[u]+w;
				pq.push({-dist[v],v});
			}
		}
	}
	int ans=dist[ID(a,b)];
	if(ans==inf) printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
skating.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&x,&y,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22