oj.uz

Submission #1002509

# Submission time Handle Problem Language Result Execution time Memory
1002509 2024-06-19T15:39:41 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 1196 ms 89932 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 dfghjk 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 = 2e5 + 123;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;

int a[N], b[N], l, r, n, k, m, w, cnt, res, sum, sum1, x, y, ans, ans1,  ind, ind1;

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);
	
    dfghjk
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
//// solved by shnurok

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14820 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14812 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14820 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14812 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 115 ms 73900 KB Output is correct
12 Correct 9 ms 17756 KB Output is correct
13 Correct 20 ms 55792 KB Output is correct
14 Correct 373 ms 74448 KB Output is correct
15 Correct 50 ms 73668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14820 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14812 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 115 ms 73900 KB Output is correct
12 Correct 9 ms 17756 KB Output is correct
13 Correct 20 ms 55792 KB Output is correct
14 Correct 373 ms 74448 KB Output is correct
15 Correct 50 ms 73668 KB Output is correct
16 Correct 74 ms 89932 KB Output is correct
17 Correct 1196 ms 85560 KB Output is correct
18 Correct 124 ms 83980 KB Output is correct
19 Correct 67 ms 84564 KB Output is correct
20 Correct 613 ms 85236 KB Output is correct