oj.uz

Submission #122407

# Submission time Handle Problem Language Result Execution time Memory
122407 2019-06-28T07:17:55 Z 김세빈(#2988) Robots (APIO13_robots) C++14
0 / 100
 982 ms 163840 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> V[303030], X[303030];
queue <pii> Q;
char S[555][555];
int chk[555][555][4];
int vis[303030];
int dp[303030][55];
int _N[10][10], _X[55], _Y[55];
int n, m, k, cnt, ans;

int dfs(int x, int y, int d)
{
	if(chk[x][y][d] >= 0) return chk[x][y][d];
	else if(chk[x][y][d] == -1) return -1;
	
	chk[x][y][d] = -1;
	
	int ret, _d;
	
	if(S[x][y] == 'A') _d = (d + 1) % 4;
	else if(S[x][y] == 'C') _d = (d + 3) % 4;
	else _d = d;
	
	if(_d == 0){
		if(x == n - 1 || S[x + 1][y] == 'x') ret = x * m + y;
		else ret = dfs(x + 1, y, _d);
	}
	else if(_d == 1){
		if(y == m - 1 || S[x][y + 1] == 'x') ret = x * m + y;
		else ret = dfs(x, y + 1, _d);
	}
	else if(_d == 2){
		if(x == 0 || S[x - 1][y] == 'x') ret = x * m + y;
		else ret = dfs(x - 1, y, _d);
	}
	else{
		if(y == 0 || S[x][y - 1] == 'x') ret = x * m + y;
		else ret = dfs(x, y - 1, _d);
	}
	
	return chk[x][y][d] = ret;
}

int main()
{
	int i, j, l, s;
	
	scanf("%d%d%d", &k, &m, &n);
	
	s = 0;
	
	for(i=1; i<=k; i++){
		for(j=i; j>=1; j--){
			_N[i][j] = s;
			_X[s] = i; _Y[s] = j;
			s ++;
		}
	}
	
	for(i=0; i<n; i++){
		scanf("%s", S[i]);
		for(j=0; j<m; j++){
			for(l=0; l<4; l++){
				chk[i][j][l] = -2;
			}
			
			for(l=0; l<k*(k+1)/2; l++){
				dp[i * m + j][l] = 1e9;
			}
			
			if('1' <= S[i][j] && S[i][j] <= '0' + k){
				dp[i * m + j][(int)(S[i][j] - '0') * (S[i][j] - '0' - 1) / 2] = 0;
				Q.push(pii(i * m + j, 0)); vis[i * m + j] = 1;
			}
		}
	}
	
	cnt ++;
	
	for(; !Q.empty(); ){
		int p = Q.front().first; Q.pop();
		for(l=0; l<4; l++){
			int t = dfs(p / m, p % m, l);
			if(t != -1 && t != p){
				V[p].push_back(t);
				if(vis[t] != cnt) Q.push(pii(t, 0));
			}
		}
	}
	
	for(i=0; i<n; i++){
		for(j=0; j<m; j++){
			for(l=0; l<4; l++){
				if(dfs(i, j, l) != -1 && dfs(i, j, l) != i * m + j){
					V[i * m + j].push_back(dfs(i, j, l));
				}
			}
		}
	}
	
	for(i=0; i<k*(k+1)/2; i++){
		int v = 1e9;
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				v = min(v, dp[j * m + l][i]);
			}
		}
		if(v == 1e9) continue;
		
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				if(dp[j * m + l][i] < v + n * m){
					X[dp[j * m + l][i] - v].push_back(j * m + l);
				}
			}
		}
		
		cnt ++; for(; !Q.empty(); Q.pop());
		
		for(j=0; j<n*m; j++){
			for(int &t: X[j]) if(vis[t] != cnt){
				vis[t] = cnt;
				Q.push(pii(t, j));
			}
			X[j].clear();
			
			for(; !Q.empty() && Q.front().second == j;){
				int p = Q.front().first; Q.pop();
				dp[p][i] = j + v;
				for(int &t: V[p]) if(vis[t] != cnt){
					Q.push(pii(t, j + 1));
					vis[t] = cnt;
				}
			}
		}
		
		int x = _X[i], y = _Y[i], z;
		
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				int id = j * m + l;
				for(z=y-1; z>=1; z--){
					dp[id][_N[x][z]] = min(dp[id][_N[x][z]], dp[id][_N[y - 1][z]] + dp[id][i]);
				}
			}
		}
	}
	
	ans = 1e9;
	
	for(i=0; i<n; i++){
		for(j=0; j<m; j++){
			ans = min(ans, dp[i * m + j][k * (k + 1) / 2 - 1]);
		}
	}
	
	if(ans < 1e9) printf("%d\n", ans);
	else printf("-1\n");
	
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &k, &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Runtime error 982 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Runtime error 982 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Runtime error 982 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Runtime error 982 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -