oj.uz

Submission #1002348

# Submission time Handle Problem Language Result Execution time Memory
1002348 2024-06-19T13:07:06 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 1122 ms 72784 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back	
#define pob pop_back
//#define int long long
#define int2 __int128_t
#define Shrek_Crush228 ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define F first
#define S second
#define sz size()
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define nep next_permutation
#define sigma signed
#define pii pair <int, int> 

using namespace std;

string alp = "abcdefghijklmnopqrstuvwxyz";
string ae = "aoeiuy";
string nums = "123456789";

const int N = 3e5 + 123;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;

int a[N], b[N], c[N], d[N], l, r, n, k, m, w, cur, cnt, res, sum, sum1, x, y, ans, ans1, mx = -inf, mn = inf, ind, ind1, pref[N], suf[N];
string s, s1;

struct RT
{
	int sum, l, r, ind;	
};
int gcd( int a, int b )
{
	return ( b ? gcd( b, a % b ) : a );
}
int lcm( int a, int b )
{
	return a / gcd( a, b ) * b;
}
int bp( int a, int b, int m )
{
	if( !b ) return 1;
	if( b & 1 ) return bp( a, b - 1, m ) * a % m;
	
	int it = bp( a, b >> 1, m );
	return it * it % m;
}
struct po
{
	int v1, v2, v3;
};
int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, -1, 0, 1 };

char maze[505][505];
pii in[505][505][5], rob[11];
vector <pii> g[505][505];
int dp[10][10][505][505];

bool may( int x, int y )
{
	if( x > n || x < 1 || y > m || y < 1 || maze[x][y] == 'x' ) return 0;
	return 1;
}
pii adj( int x, int y, int tp )
{
    if( in[x][y][tp].F ) return in[x][y][tp]; in[x][y][tp] = { -inf, -inf };
    
    int copy = tp;
    
    if( maze[x][y] == 'C' ) tp = ( tp + 1 ) % 4;
    if( maze[x][y] == 'A' ) tp = ( tp + 3 ) % 4;
    
    int xt = x + dx[tp], yt = y + dy[tp];
    
    if( may( xt, yt )) return in[x][y][copy] = adj( xt, yt, tp );
    if( !may( xt, yt )) return in[x][y][copy] = { x, y };
}
void solve()
{
	cin >> k >> m >> n;
	int x1, y1, x2, y2;	
	
	vector <pii> qu;
	
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 ) 
		{
			cin >> maze[i][j];
			if( maze[i][j] >= '1' && maze[i][j] <= '9' ) rob[maze[i][j] - '0'] = { i, j };		
		}
	}
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 )
		{
			FOR( tp, 0, 3, 1 )
			{
				if( !may( i, j ) ) continue;
				
				pii brat = adj( i, j, tp );
				
				if( brat.F != -inf ) g[i][j].pb( brat );
			}
		}
	}
	FOR( l, 1, k, 1 )
	{
		FOR( r, l, k, 1 )
		{
			FOR( i, 1, n, 1 )
			{
				FOR( j, 1, m, 1	) dp[l][r][i][j] = inf;
			}
		}
	}
	FOR( id, 1, k, 1 ) dp[id][id][rob[id].F][rob[id].S] = 0;
	
	FOR( otrezok, 1, k, 1 )
	{
		FOR( l, 1, k, 1 )
		{
			if( otrezok + l - 1 > k ) break;
			// r - l + 1 = otrezok
			r = otrezok + l - 1;
			
			FOR( i, 1, n, 1 )
			{
				FOR( j, 1, m, 1 ) 
				{
					FOR( md, l, r - 1, 1 ) dp[l][r][i][j] = min( dp[l][r][i][j], dp[l][md][i][j] + dp[md + 1][r][i][j] );
				}
			}
			priority_queue <pair <int, pii>> q;
			
			FOR( i, 1, n, 1 )
			{
				FOR( j, 1, m, 1 ) 
				{
					if( dp[l][r][i][j] != inf ) q.push({ -dp[l][r][i][j], { i, j }});
				}
			}
			while( q.sz )
			{
				pair <int, pii> v = q.top();
				q.pop();
				
				for( auto to : g[v.S.F][v.S.S] )
				{
					if( dp[l][r][to.F][to.S] > dp[l][r][v.S.F][v.S.S] + 1 ) 
					{
						dp[l][r][to.F][to.S] = dp[l][r][v.S.F][v.S.S] + 1;
						q.push({ -dp[l][r][to.F][to.S], to });
					}
				}
			} 
		}
	}
	res = inf;
	
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 ) res = min( res, dp[1][k][i][j] );
	}
	if( res == inf ) res = -1;
	cout << res << '\n';
}
sigma main() 
{
	//freopen("haircut.in", "r", stdin);
	//freopen("haircut.out", "w", stdout);
	
    Shrek_Crush228
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
//// solved by KluydQ
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Compilation message

robots.cpp: In function 'std::pair<int, int> adj(int, int, int)':
robots.cpp:80:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   80 |     if( in[x][y][tp].F ) return in[x][y][tp]; in[x][y][tp] = { -inf, -inf };
      |     ^~
robots.cpp:80:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   80 |     if( in[x][y][tp].F ) return in[x][y][tp]; in[x][y][tp] = { -inf, -inf };
      |                                               ^~
robots.cpp: In function 'void solve()':
robots.cpp:95:6: warning: unused variable 'x1' [-Wunused-variable]
   95 |  int x1, y1, x2, y2;
      |      ^~
robots.cpp:95:10: warning: unused variable 'y1' [-Wunused-variable]
   95 |  int x1, y1, x2, y2;
      |          ^~
robots.cpp:95:14: warning: unused variable 'x2' [-Wunused-variable]
   95 |  int x1, y1, x2, y2;
      |              ^~
robots.cpp:95:18: warning: unused variable 'y2' [-Wunused-variable]
   95 |  int x1, y1, x2, y2;
      |                  ^~
robots.cpp: In function 'std::pair<int, int> adj(int, int, int)':
robots.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 88 ms 39724 KB Output is correct
12 Correct 13 ms 12892 KB Output is correct
13 Correct 26 ms 30292 KB Output is correct
14 Correct 365 ms 40308 KB Output is correct
15 Correct 61 ms 39444 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 88 ms 39724 KB Output is correct
12 Correct 13 ms 12892 KB Output is correct
13 Correct 26 ms 30292 KB Output is correct
14 Correct 365 ms 40308 KB Output is correct
15 Correct 61 ms 39444 KB Output is correct
16 Correct 91 ms 72784 KB Output is correct
17 Correct 1122 ms 68032 KB Output is correct
18 Correct 154 ms 66468 KB Output is correct
19 Correct 83 ms 67412 KB Output is correct
20 Correct 571 ms 67512 KB Output is correct