oj.uz

Submission #159158

# Submission time Handle Problem Language Result Execution time Memory
159158 2019-10-21T09:59:27 Z TadijaSebez None (JOI16_skating) C++11
100 / 100
 703 ms 217724 KB 
#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;}
int U[N][N],D[N][N],L[N][N],R[N][N];
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 L[i][j]=ID(i,k);
		}
		for(int j=m,k=m;j>=1;j--)
		{
			if(base[i][j]=='#') k=j-1;
			else R[i][j]=ID(i,k);
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1,k=1;j<=n;j++)
		{
			if(base[j][i]=='#') k=j+1;
			else U[j][i]=ID(k,i);
		}
		for(int j=n,k=n;j>=1;j--)
		{
			if(base[j][i]=='#') k=j-1;
			else D[j][i]=ID(k,i);
		}
	}
	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});
		E[ID(i,j)].pb({L[i][j],1});
		E[ID(i,j)].pb({R[i][j],1});
		E[ID(i,j)].pb({U[i][j],1});
		E[ID(i,j)].pb({D[i][j],1});
	}
	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;
	queue<int> q[2];
	q[0].push(ID(x,y));
	dist[ID(x,y)]=0;
	while(q[0].size()+q[1].size())
	{
		int u;
		if(q[0].empty() || (q[1].size() && dist[q[1].front()]<dist[q[0].front()]))
		{
			u=q[1].front();
			q[1].pop();
		}
		else
		{
			u=q[0].front();
			q[0].pop();
		}
		if(was[u]) continue;
		was[u]=1;
		for(auto e:E[u])
		{
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w)
			{
				q[w-1].push(v);
				dist[v]=dist[u]+w;
			}
		}
	}
	int ans=dist[ID(a,b)];
	if(ans==inf) printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:16: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:17: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:56: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 121436 KB Output is correct
2 Correct 112 ms 121304 KB Output is correct
3 Correct 113 ms 121336 KB Output is correct
4 Correct 112 ms 121372 KB Output is correct
5 Correct 113 ms 121340 KB Output is correct
6 Correct 112 ms 121300 KB Output is correct
7 Correct 132 ms 121464 KB Output is correct
8 Correct 112 ms 121336 KB Output is correct
9 Correct 97 ms 104028 KB Output is correct
10 Correct 112 ms 121336 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 121436 KB Output is correct
2 Correct 112 ms 121304 KB Output is correct
3 Correct 113 ms 121336 KB Output is correct
4 Correct 112 ms 121372 KB Output is correct
5 Correct 113 ms 121340 KB Output is correct
6 Correct 112 ms 121300 KB Output is correct
7 Correct 132 ms 121464 KB Output is correct
8 Correct 112 ms 121336 KB Output is correct
9 Correct 97 ms 104028 KB Output is correct
10 Correct 112 ms 121336 KB Output is correct
11 Correct 132 ms 127792 KB Output is correct
12 Correct 130 ms 127736 KB Output is correct
13 Correct 130 ms 127712 KB Output is correct
14 Correct 127 ms 126968 KB Output is correct
15 Correct 122 ms 126148 KB Output is correct
16 Correct 130 ms 127608 KB Output is correct
17 Correct 128 ms 127224 KB Output is correct
18 Correct 126 ms 126840 KB Output is correct
19 Correct 128 ms 127224 KB Output is correct
20 Correct 131 ms 127452 KB Output is correct
21 Correct 126 ms 126712 KB Output is correct
22 Correct 121 ms 125696 KB Output is correct
23 Correct 127 ms 126932 KB Output is correct
24 Correct 130 ms 127568 KB Output is correct
25 Correct 126 ms 126712 KB Output is correct
26 Correct 128 ms 126712 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 121436 KB Output is correct
2 Correct 112 ms 121304 KB Output is correct
3 Correct 113 ms 121336 KB Output is correct
4 Correct 112 ms 121372 KB Output is correct
5 Correct 113 ms 121340 KB Output is correct
6 Correct 112 ms 121300 KB Output is correct
7 Correct 132 ms 121464 KB Output is correct
8 Correct 112 ms 121336 KB Output is correct
9 Correct 97 ms 104028 KB Output is correct
10 Correct 112 ms 121336 KB Output is correct
11 Correct 132 ms 127792 KB Output is correct
12 Correct 130 ms 127736 KB Output is correct
13 Correct 130 ms 127712 KB Output is correct
14 Correct 127 ms 126968 KB Output is correct
15 Correct 122 ms 126148 KB Output is correct
16 Correct 130 ms 127608 KB Output is correct
17 Correct 128 ms 127224 KB Output is correct
18 Correct 126 ms 126840 KB Output is correct
19 Correct 128 ms 127224 KB Output is correct
20 Correct 131 ms 127452 KB Output is correct
21 Correct 126 ms 126712 KB Output is correct
22 Correct 121 ms 125696 KB Output is correct
23 Correct 127 ms 126932 KB Output is correct
24 Correct 130 ms 127568 KB Output is correct
25 Correct 126 ms 126712 KB Output is correct
26 Correct 128 ms 126712 KB Output is correct
27 Correct 703 ms 217640 KB Output is correct
28 Correct 641 ms 217724 KB Output is correct
29 Correct 683 ms 217372 KB Output is correct
30 Correct 551 ms 209912 KB Output is correct
31 Correct 331 ms 176632 KB Output is correct
32 Correct 679 ms 217484 KB Output is correct
33 Correct 210 ms 146460 KB Output is correct
34 Correct 434 ms 206200 KB Output is correct
35 Correct 612 ms 216072 KB Output is correct
36 Correct 492 ms 207116 KB Output is correct
37 Correct 430 ms 193912 KB Output is correct
38 Correct 644 ms 217208 KB Output is correct
39 Correct 452 ms 191464 KB Output is correct
40 Correct 262 ms 165628 KB Output is correct