oj.uz

Submission #152006

# Submission time Handle Problem Language Result Execution time Memory
152006 2019-09-05T20:27:08 Z TadijaSebez Robots (APIO13_robots) C++11
100 / 100
 858 ms 138676 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=501;
const int H=500*500+1;
const int inf=1e9+7;
int n,m,k,nm;
int ID(int x, int y){ return (x-1)*m+y;}
int go[N][N][4],Move[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
char base[N][N];
int Get(int x, int y, int d)
{
	if(base[x][y]=='x' || x==0 || y==0 || x>n || y>m) return ID(x-Move[d][0],y-Move[d][1]);
	if(go[x][y][d]) return go[x][y][d];
	go[x][y][d]=-1;
	if(base[x][y]=='A') go[x][y][d]=Get(x+Move[(d+1)%4][0],y+Move[(d+1)%4][1],(d+1)%4);
	else if(base[x][y]=='C') go[x][y][d]=Get(x+Move[(d+3)%4][0],y+Move[(d+3)%4][1],(d+3)%4);
	else go[x][y][d]=Get(x+Move[d][0],y+Move[d][1],d);
	return go[x][y][d];
}
vector<int> E[H];
int dist[10][10][H];
void BFS(int st, int id)
{
	queue<int> q;
	for(int i=1;i<=nm;i++) dist[id][id][i]=-1;
	dist[id][id][st]=0;
	q.push(st);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int y:E[x]) if(dist[id][id][y]==-1)
		{
			dist[id][id][y]=dist[id][id][x]+1;
			q.push(y);
		}
	}
	for(int i=1;i<=nm;i++) if(dist[id][id][i]==-1) dist[id][id][i]=inf;
}
int tmp_d[H];
vector<int> q[H*10];
void Dijkstra()
{
	int mn=inf,work=0;
	for(int i=1;i<=nm;i++) if(tmp_d[i]!=inf) q[tmp_d[i]].pb(i),mn=min(mn,tmp_d[i]),work++;
	for(int ptr=mn;ptr<H*10 && work>0;ptr++)
	{
		while(q[ptr].size())
		{
			int x=q[ptr].back();
			q[ptr].pop_back();
			if(ptr!=tmp_d[x]) continue;
			work--;
			for(int y:E[x]) if(tmp_d[y]>tmp_d[x]+1)
			{
				tmp_d[y]=tmp_d[x]+1;
				if(tmp_d[y]>=H*10) continue;
				q[tmp_d[y]].pb(y);
				work++;
			}
		}
	}
}
int main()
{
	scanf("%i %i %i",&k,&m,&n);nm=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;j<=m;j++)
	{
		for(int d=0;d<4;d++)
		{
			if(Get(i,j,d)!=-1) E[ID(i,j)].pb(go[i][j][d]);
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]>='1' && base[i][j]<='9')
	{
		int id=base[i][j]-'0';
		BFS(ID(i,j),id);
	}
	for(int len=2;len<=k;len++) for(int i=1;i<=k-len+1;i++)
	{
		int j=i+len-1;
		for(int u=1;u<=nm;u++) dist[i][j][u]=inf;
		for(int z=i;z<j;z++)
		{
			for(int u=1;u<=nm;u++) if(dist[i][z][u]!=-1 && dist[z+1][j][u]!=-1)
			{
				int sum=dist[i][z][u]+dist[z+1][j][u];
				if(dist[i][j][u]==-1 || sum<dist[i][j][u]) dist[i][j][u]=sum;
			}
		}
		for(int u=1;u<=nm;u++) tmp_d[u]=dist[i][j][u];
		Dijkstra();
		for(int u=1;u<=nm;u++) dist[i][j][u]=tmp_d[u];
	}
	int ans=-1;
	for(int u=1;u<=nm;u++) if(dist[1][k][u]!=inf)
	{
		if(ans==-1 || ans>dist[1][k][u]) ans=dist[1][k][u];
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&k,&m,&n);nm=n*m;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
robots.cpp:68: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);
                        ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 64888 KB Output is correct
2 Correct 60 ms 64888 KB Output is correct
3 Correct 60 ms 64860 KB Output is correct
4 Correct 61 ms 65024 KB Output is correct
5 Correct 60 ms 65016 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 64888 KB Output is correct
2 Correct 60 ms 64888 KB Output is correct
3 Correct 60 ms 64860 KB Output is correct
4 Correct 61 ms 65024 KB Output is correct
5 Correct 60 ms 65016 KB Output is correct
6 Correct 67 ms 64888 KB Output is correct
7 Correct 61 ms 64888 KB Output is correct
8 Correct 67 ms 65016 KB Output is correct
9 Correct 67 ms 64888 KB Output is correct
10 Correct 66 ms 64932 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 64888 KB Output is correct
2 Correct 60 ms 64888 KB Output is correct
3 Correct 60 ms 64860 KB Output is correct
4 Correct 61 ms 65024 KB Output is correct
5 Correct 60 ms 65016 KB Output is correct
6 Correct 67 ms 64888 KB Output is correct
7 Correct 61 ms 64888 KB Output is correct
8 Correct 67 ms 65016 KB Output is correct
9 Correct 67 ms 64888 KB Output is correct
10 Correct 66 ms 64932 KB Output is correct
11 Correct 284 ms 88716 KB Output is correct
12 Correct 83 ms 70392 KB Output is correct
13 Correct 263 ms 80680 KB Output is correct
14 Correct 544 ms 91028 KB Output is correct
15 Correct 233 ms 86976 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 64888 KB Output is correct
2 Correct 60 ms 64888 KB Output is correct
3 Correct 60 ms 64860 KB Output is correct
4 Correct 61 ms 65024 KB Output is correct
5 Correct 60 ms 65016 KB Output is correct
6 Correct 67 ms 64888 KB Output is correct
7 Correct 61 ms 64888 KB Output is correct
8 Correct 67 ms 65016 KB Output is correct
9 Correct 67 ms 64888 KB Output is correct
10 Correct 66 ms 64932 KB Output is correct
11 Correct 284 ms 88716 KB Output is correct
12 Correct 83 ms 70392 KB Output is correct
13 Correct 263 ms 80680 KB Output is correct
14 Correct 544 ms 91028 KB Output is correct
15 Correct 233 ms 86976 KB Output is correct
16 Correct 507 ms 122056 KB Output is correct
17 Correct 858 ms 138676 KB Output is correct
18 Correct 303 ms 124404 KB Output is correct
19 Correct 499 ms 122352 KB Output is correct
20 Correct 672 ms 130368 KB Output is correct