oj.uz

Submission #1002332

# Submission time Handle Problem Language Result Execution time Memory
1002332 2024-06-19T12:47:35 Z vjudge1 Robots (APIO13_robots) C++17
10 / 100
 96 ms 163840 KB 
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<deque>


using namespace std;
#define int long long
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)

const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int n , w , h;
char a[505][505];
int dp[15][505][505];
int tmp = 1;
int used[505][505][11] , use[505][505];
pii p[15][505][505];
int rev(int x){
	if(x == 1)x = 3;
	else if(x == 3)x = 2;
	else if(x == 2)x = 4;
	else if(x == 4)x = 1;
	return x;
}
int inv(int x){
	if(x == 1)x = 4;
	else if(x == 4)x = 2;
	else if(x == 2)x = 3;
	else if(x == 3)x = 1;
	return x;
}
set<pii> g[505][505];

pii build(int x , int y , int k){
	if((k == 1 and (y + 1 > w or a[x][y + 1] == 'x')) or (k == 2 and (y - 1 <= 0 or a[x][y - 1] == 'x')) or (k == 3 and (x - 1 <= 0 or a[x - 1][y] == 'x')) or (k == 4 and (x + 1 > h or a[x + 1][y] == 'x'))){
		if(k != 1 and !(y + 1 > w or a[x][y + 1] == 'x') and !used[x][y + 1][1])g[x][y].insert(build(x , y , 1));
		if(k != 2 and !((y - 1 <= 0 or a[x][y - 1] == 'x')) and !used[x][y - 1][2])g[x][y].insert(build(x , y , 2));
		if(k != 3 and !(x - 1 <= 0 or a[x - 1][y] == 'x') and !used[x - 1][y][3])g[x][y].insert(build(x , y , 3));
		if(k != 4 and !(x + 1 > h or a[x + 1][y] == 'x') and !used[x + 1][y][4])g[x][y].insert(build(x , y , 4));
		return {x , y};
	}
	if(k == 1)y++;
	if(k == 2)y--;
	if(k == 3)x--;
	if(k == 4)x++;
	if(a[x][y] == 'A')k = rev(k);
	else if(a[x][y] == 'C')k = inv(k);
	used[x][y][k] = 1;
	return build(x , y , k);
}
pair<int , pii> calc(int x , int y , int cur){
		while(1){
			if(a[x][y] == 'A'){
				cur = rev(cur);
			}
			else if(a[x][y] == 'C'){
				cur = inv(cur);
			}
			if(cur == 1){
				if(a[x][y + 1] == 'x' or y + 1 > w)break;
				y++;
			}
			else if(cur == 2){
				if(a[x][y - 1] == 'x' or y - 1 == 0)break;
				y--;
			}
			else if(cur == 3){
				if(a[x - 1][y] == 'x' or x - 1 == 0)break;
				x--;
			}
			else if(cur == 4){
				if(a[x + 1][y] == 'x' or x + 1 > h)break;
				x++;
			}
		}
		return {x , {y , cur}};	
}

void dfs(int x , int y){
	use[x][y] = 1;
	//if(tmp == 2)cout << x << ' ' << y << '\n';
	queue<pii> q;
	q.push({x , y});
	while(len(q)){
		int v = q.front().F , u = q.front().S;
		use[v][u] = 1;
		q.pop();
		pair<int , pii> cc = calc(v , u , 1);
		int x1 = cc.F , y1 = cc.S.F;
		if(!use[x1][y1]){
			q.push({x1 , y1});
			if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
				dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
			
			}
			 g[v][u].insert({x1 , y1});
			 g[x1][y1].insert({v , u});
		}
		cc = calc(v , u , 2);
		x1 = cc.F , y1 = cc.S.F;
		if(!use[x1][y1]){
			q.push({x1 , y1});
			if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
				dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
				
			}
			 g[v][u].insert({x1 , y1});
			 g[x1][y1].insert({v , u});
		}
		cc = calc(v , u , 3);
		x1 = cc.F , y1 = cc.S.F;
		if(!use[x1][y1]){
			q.push({x1 , y1});
			if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
				dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
				
			}
			 g[v][u].insert({x1 , y1});
			 g[x1][y1].insert({v , u});
		}
		cc = calc(v , u , 4);
		x1 = cc.F , y1 = cc.S.F;
		if(!use[x1][y1]){
			q.push({x1 , y1});
			if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
				dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
				
			}
			 g[v][u].insert({x1 , y1});
			 g[x1][y1].insert({v , u});
		}
	}

}
//1 >
//2 <
//3 ^
//4 v
bool cmp(pii x , pii y){
	return a[x.F][x.S] < a[y.F][y.S];
}
int ans[12][12][505][505];
void skibidi_dop_dop_dop_yes_yes(){
	cin >> n >> w >> h;
	vector<pii> v;
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			cin >> a[i][j];
			dp[1][i][j] = dp[2][i][j] = dp[3][i][j] = dp[4][i][j] = dp[5][i][j] = dp[6][i][j] = dp[7][i][j] = dp[8][i][j] = dp[9][i][j] = inf;
			if(a[i][j] >= '1' and a[i][j] <= '9')v.pb({i , j});
		}
	}
	sort(all(v) , cmp);
	for(auto it : v){
		g[it.F][it.S].insert(build(it.F , it.S , 1));
		g[it.F][it.S].insert(build(it.F , it.S , 2));
		g[it.F][it.S].insert(build(it.F , it.S , 3));
		g[it.F][it.S].insert(build(it.F , it.S , 4));
	}
	for(auto it : v){
		dp[tmp][it.F][it.S] = 0;
		dfs(it.F , it.S);
		tmp++;
		for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)use[i][j] = 0;
		//break;
	}
	int mn = inf;
	if(n == 1){
		cout << 0;
		return;
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = 1 ; r <= n ; r++){
					ans[i][j][l][r] = inf;
				}
			}
		}
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int k = 1 ; k <= n ; k++){
				ans[i][j][k][k] = dp[k][i][j];
			}
		}
		
		//cout << '\n';
	}	
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = l + 1 ; r <= n ; r++){
					for(int md = l ; md < r ; md++){
						ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
					}
				}
			}
		}
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = l + 1 ; r <= n ; r++){
					for(int md = l ; md < r ; md++){
						for(auto it : g[i][j]){
							ans[i][j][l][r] = min(ans[i][j][l][r] , ans[it.F][it.S][l][r] + 1);
						}
					
					}
				}
			}
		}
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = l + 1 ; r <= n ; r++){
					for(int md = l ; md < r ; md++){
						ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
					}
				}
			}
		}
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = l + 1 ; r <= n ; r++){
					for(int md = l ; md < r ; md++){
						ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
					}
				}
			}
		}
	}	
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			for(int l = 1 ; l <= n ; l++){
				for(int r = l + 1 ; r <= n ; r++){
					for(int md = l ; md < r ; md++){
						ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
					}
				}
			}
		}
	}			
 	int mx = inf;
 	//cout << ans[1][7][3][4];
 //	for(auto it : g[1][1])cout << it.F << ' ' << it.S << '\n';
 	for(int i = 1 ; i <= h ; i++){
 		for(int j = 1 ; j <= w ; j++){
 			//cout << ans[i][j][1][n] << ' ';
 			mx = min(mx , ans[i][j][1][n]);
 		}
 	//	cout << '\n';
 	}
 	if(mx < inf)cout << mx;
 	else cout << -1;
	
}

signed main(){
	int t = 1;
	Bekabot
	while(t--)skibidi_dop_dop_dop_yes_yes();
}

Compilation message

robots.cpp: In function 'void skibidi_dop_dop_dop_yes_yes()':
robots.cpp:177:6: warning: unused variable 'mn' [-Wunused-variable]
  177 |  int mn = inf;
      |      ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12584 KB Output is correct
4 Correct 5 ms 13916 KB Output is correct
5 Correct 5 ms 13916 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12584 KB Output is correct
4 Correct 5 ms 13916 KB Output is correct
5 Correct 5 ms 13916 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Runtime error 96 ms 163840 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12584 KB Output is correct
4 Correct 5 ms 13916 KB Output is correct
5 Correct 5 ms 13916 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Runtime error 96 ms 163840 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12584 KB Output is correct
4 Correct 5 ms 13916 KB Output is correct
5 Correct 5 ms 13916 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Runtime error 96 ms 163840 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -