oj.uz

Submission #1002444

# Submission time Handle Problem Language Result Execution time Memory
1002444 2024-06-19T14:58:10 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 1403 ms 82744 KB 
#include <bits/stdc++.h>

using namespace std;
using ll  =  long long;

#ifdef U_U
#include "algo/debug.h"
#else
#define deb(x...) 42
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define szof(x) (int)x.size()
//#define int ll
#define love bool

template<class T> void MIN(T& a, const T b) { b < a ? a = b, 1 : 0; }
template<class T> void MAX(T& a, const T b) { a < b ? a = b, 1 : 0; }

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int inf = 1e9;
//2147483647;
const int INF = 9223372036854775807;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
// Follow the white rabbit.

int n, m, nn;
char e[505][505];
int dist[505][505][10];
vector <pair <int, int> > g[505][505];
vector <pair <int, int> > v(11);
pair <int, int> was[505][505][10];
bool can (int x, int y) {
	if (x > n || x < 1 || y > m || y < 1 || e[x][y] == 'x') return 0;
	return 1;
}
pair <int, int> get (int x, int y, int k) {
	if (was[x][y][k].first) return was[x][y][k];
	was[x][y][k] = {-1, -1};
	int tmp = k;
	if (e[x][y] == 'A') k += 3, k %= 4;
	if (e[x][y] == 'C') k ++, k %= 4;
	int X = dx[k] + x, Y = dy[k] + y;
	if (can(X, Y)) {
		return was[x][y][tmp] = get(X, Y, k);
	}
	return was[x][y][tmp] = {x, y};
}
int dp[10][10][505][505];
void ka () {
	cin >> nn >> m >> n;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> e[i][j];
			if (e[i][j] >= '1' && e[i][j] <= '9') v[e[i][j] - '0'] = {i, j};
		}
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (!can(i, j)) continue;
			for (int k = 0; k < 4; k ++) {
				pair <int, int> tmp = get(i, j, k);
				if (tmp.first != -1) g[i][j].pb(tmp);
			}		
		}
	}
	for (int l = 1; l <= nn; l ++) {
		for (int r = l; r <= nn; r ++) {
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {
					dp[l][r][i][j] = inf;
				}
			}
		}
	}
	for (int i = 1; i <= nn; i ++) {
		dp[i][i][v[i].first][v[i].second] = 0;
	}
	for (int len = 1; len <= nn; len ++) {
		for (int l = 1; l <= nn; l ++) {
			int r = l + len - 1;
			if (r > nn) break;
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {				
					for (int md = l; md < r; md ++) {
						MIN(dp[l][r][i][j], dp[l][md][i][j] + dp[md + 1][r][i][j]);
					}
				}
			}
			set <pair <int, pair <int, int> > > q;
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {
					if (dp[l][r][i][j] != inf) q.insert({dp[l][r][i][j], {i, j}});
				}
			}
			while (szof(q)) {
				pair <int, pair <int, int> > tmp = *q.begin();
				q.erase(tmp);
				for (pair <int, int> c : g[tmp.second.first][tmp.second.second]) {
					if (dp[l][r][c.first][c.second] > dp[l][r][tmp.second.first][tmp.second.second] + 1) {
						q.erase({dp[l][r][c.first][c.second], c});
						dp[l][r][c.first][c.second] = dp[l][r][tmp.second.first][tmp.second.second] + 1;
						q.insert({dp[l][r][c.first][c.second], c});
					}
				}
			}
		}
	}
	int ans = inf;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) MIN(ans, dp[1][nn][i][j]);
	cout << (ans == inf ? -1 : ans);
}

const bool overflow = 0;

main() {
  //freopen("haircut.in"	, "r", stdin); freopen("haircut.out", "w", stdout);
  cout.setf(ios::fixed);cout.precision(12);
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int tc = 1; 
  if (overflow) cin >> tc;
  for (int cs = 1; cs <= tc; cs ++) {
		#ifdef U_U
		cout << ":D\n";
		#endif
		ka();
		//if (cs != tc) cout << '\n';
  }
}

Compilation message

robots.cpp:25:17: warning: overflow in conversion from 'long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   25 | const int INF = 9223372036854775807;
      |                 ^~~~~~~~~~~~~~~~~~~
robots.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6236 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6492 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 4 ms 6236 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 4 ms 6236 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 3 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 4 ms 6236 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 4 ms 6236 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 127 ms 43092 KB Output is correct
12 Correct 13 ms 15196 KB Output is correct
13 Correct 36 ms 33720 KB Output is correct
14 Correct 577 ms 44020 KB Output is correct
15 Correct 105 ms 41956 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6236 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 4 ms 6236 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 127 ms 43092 KB Output is correct
12 Correct 13 ms 15196 KB Output is correct
13 Correct 36 ms 33720 KB Output is correct
14 Correct 577 ms 44020 KB Output is correct
15 Correct 105 ms 41956 KB Output is correct
16 Correct 149 ms 82744 KB Output is correct
17 Correct 1403 ms 79280 KB Output is correct
18 Correct 167 ms 75120 KB Output is correct
19 Correct 83 ms 77316 KB Output is correct
20 Correct 844 ms 76624 KB Output is correct