oj.uz

Submission #1093954

# Submission time Handle Problem Language Result Execution time Memory
1093954 2024-09-28T06:47:07 Z Trisanu_Das Robots (APIO13_robots) C++17
100 / 100
 936 ms 57536 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
 
const int inf = 1e9, N = 505;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
 
int n, w, h, dt[9][9][N][N];
char ipt[N][N];
 
bool vis[N][N][4], solved[9][9];
 
 
pii ini[9], nxt[N][N][4];
queue<pii>q;
 
vector<pair<int,pii> > vec;
 
bool valid (int A, int B) {
	if(A < 1 || A > h) return false;
	if(B < 1 || B > w) return false;
	if(ipt[A][B] == 'x') return false;
	return true;
}
 
void calc(int A, int B, int i) {
	if(vis[A][B][i]) return;
	vis[A][B][i] = true;
	int nA = A+dx[i], nB = B+dy[i];
	if(!valid(nA,nB)) {
		nxt[A][B][i] = {A,B};
		return;
	}
	if(ipt[nA][nB]=='C') {
		calc(nA, nB, (i+1)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+1)%4];
	}
	else if(ipt[nA][nB]=='A') {
		calc(nA, nB, (i+3)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+3)%4];
	}
	else {
		calc(nA, nB, i);
		nxt[A][B][i] = nxt[nA][nB][i];
	}
}
 
void solve(int S, int E) {
	if(solved[S][E]) return;
	solved[S][E] = true;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			dt[S][E][i][j] = inf;
		}
	}
	if(S == E) dt[S][E][ini[S].X][ini[S].Y] = 0;
	for(int k=S;k<E;k++) {
		solve(S,k);
		solve(k+1,E);
		for(int i=1;i<=h;i++) {
			for(int j=1;j<=w;j++) {
				dt[S][E][i][j] = min({inf, dt[S][E][i][j], dt[S][k][i][j] + dt[k+1][E][i][j]});
			}
		}
	}
	vec.clear();
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			vec.push_back({dt[S][E][i][j], {i, j}});
		}
	}
	sort(vec.begin(),vec.end());
	for(int k=0;k<vec.size();k++) {
		if(dt[S][E][vec[k].Y.X][vec[k].Y.Y] < vec[k].X) continue;
		q.push(vec[k].Y);
		while(!q.empty()) {
			int A, B;
			tie(A, B) = q.front();
			q.pop();
			for(int i=0;i<4;i++) {
				int nA, nB;
				tie(nA, nB) = nxt[A][B][i];
				if(dt[S][E][A][B] + 1 < dt[S][E][nA][nB]) {
					dt[S][E][nA][nB] = dt[S][E][A][B] + 1;
					q.push({nA, nB});
				}
			}
		}
	}
}
 
int main()
{
	scanf("%d%d%d",&n,&w,&h);
	for(int i=1;i<=h;i++) {
		scanf("%s",ipt[i]+1);
		for(int j=1;j<=w;j++) {
			if('1' <= ipt[i][j] && ipt[i][j] <= '9') {
				ini[ipt[i][j]-'1'] = {i, j};
			}
		}
	}
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			for(int k=0;k<4;k++) {
				calc(i,j,k);
			}
		}
	}
	solve(0,n-1);
	int ans = inf;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			ans = min(ans, dt[0][n-1][i][j]);
		}
	}
	printf("%d\n", ans == inf ? -1 : ans);
}

Compilation message

robots.cpp: In function 'void solve(int, int)':
robots.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int k=0;k<vec.size();k++) {
      |              ~^~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d%d",&n,&w,&h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%s",ipt[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 270 ms 32964 KB Output is correct
12 Correct 10 ms 7384 KB Output is correct
13 Correct 189 ms 23072 KB Output is correct
14 Correct 286 ms 32960 KB Output is correct
15 Correct 240 ms 32964 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 270 ms 32964 KB Output is correct
12 Correct 10 ms 7384 KB Output is correct
13 Correct 189 ms 23072 KB Output is correct
14 Correct 286 ms 32960 KB Output is correct
15 Correct 240 ms 32964 KB Output is correct
16 Correct 666 ms 57364 KB Output is correct
17 Correct 833 ms 57532 KB Output is correct
18 Correct 649 ms 57536 KB Output is correct
19 Correct 936 ms 57408 KB Output is correct
20 Correct 771 ms 57496 KB Output is correct