| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246998 |
2020-07-10T17:27:07 Z |
keko37 |
Robots (APIO13_robots) |
C++14 |
|
326 ms |
41476 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 505;
int n, h, w, sol = 1e9;
int robot[20];
char a[MAXN][MAXN];
pi nxt[MAXN*MAXN][4];
int to[MAXN*MAXN][4], bio[MAXN * MAXN];
int dist[MAXN * MAXN][10][10];
vector <int> v, r[MAXN * MAXN];
queue <int> q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool ok (int x, int y) {
return 0 <= x && x < h && 0 <= y && y < w;
}
void build_succesor () {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] == 'x') continue;
for (int d = 0; d < 4; d++) {
int nx, ny, nd;
nd = (a[i][j] == 'A' ? (d + 3) % 4 : (a[i][j] == 'C' ? (d + 1) % 4 : d));
nx = i + dx[nd];
ny = j + dy[nd];
if (!ok(nx, ny) || a[nx][ny] == 'x') {
nxt[i*w+j][d] = {i*w+j, -1};
} else {
nxt[i*w+j][d] = {nx*w+ny, nd};
}
}
}
}
}
int get_sink (int node, int d) {
if (to[node][d] >= 0) return to[node][d];
to[node][d] = -2;
if (nxt[node][d].second == -1) {
return to[node][d] = nxt[node][d].first;
} else {
int succ = nxt[node][d].first, nd = nxt[node][d].second;
if (to[succ][nd] == -2) {
return to[node][d] = -3;
} else {
return to[node][d] = get_sink(succ, nd);
}
}
}
void build_graph () {
memset(to, -1, sizeof to);
for (int i = 0; i < n; i++) {
q.push(robot[i]);
bio[robot[i]] = 1;
}
while (!q.empty()) {
int x = q.front();
q.pop();
v.push_back(x);
for (int d = 0; d < 4; d++) {
int sus = get_sink(x, d);
if (!bio[sus]) {
q.push(sus);
bio[sus] = 1;
}
}
}
}
void solve (int lo, int hi) {
for (auto x : v) dist[x][lo][hi] = 1e9;
int mn = 0;
if (lo == hi) {
dist[robot[lo]][lo][lo] = 0;
mn = 0;
} else {
for (auto x : v) {
for (int i = lo; i < hi; i++) {
int val = dist[x][lo][i] + dist[x][i + 1][hi];
dist[x][lo][hi] = min(dist[x][lo][hi], val);
}
mn = min(mn, dist[x][lo][hi]);
}
}
for (auto x : v) {
bio[x] = 0;
int val = dist[x][lo][hi] - mn;
if (val < v.size()) r[val].push_back(x);
}
for (int i = 0; i < v.size(); i++) {
while (!r[i].empty()) {
int x = r[i].back();
r[i].pop_back();
if (!bio[x]) {
q.push(x);
bio[x] = 1;
}
}
while (!q.empty()) {
int x = q.front(), len = dist[x][lo][hi];
if (len != mn + i) break;
q.pop();
for (int d = 0; d < 4; d++) {
int sus = to[x][d];
if (sus >= 0 && !bio[sus]) {
q.push(sus);
bio[sus] = 1;
dist[sus][lo][hi] = len + 1;
}
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w >> h;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> a[i][j];
if ('1' <= a[i][j] && a[i][j] <= '9') {
robot[a[i][j] - '1'] = i*w+j;
}
}
}
build_succesor();
build_graph();
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
solve(i, i + len - 1);
}
}
for (auto x : v) sol = min(sol, dist[x][0][n - 1]);
if (sol == 1e9) cout << -1; else cout << sol;
return 0;
}
Compilation message
robots.cpp: In function 'void solve(int, int)':
robots.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (val < v.size()) r[val].push_back(x);
~~~~^~~~~~~~~~
robots.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10368 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10368 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 7 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 8 |
Correct |
12 ms |
10368 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10368 KB |
Output is correct |
| 10 |
Correct |
11 ms |
10496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10368 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 7 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 8 |
Correct |
12 ms |
10368 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10368 KB |
Output is correct |
| 10 |
Correct |
11 ms |
10496 KB |
Output is correct |
| 11 |
Correct |
133 ms |
38264 KB |
Output is correct |
| 12 |
Correct |
27 ms |
36608 KB |
Output is correct |
| 13 |
Correct |
18 ms |
13696 KB |
Output is correct |
| 14 |
Incorrect |
326 ms |
41476 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10368 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 7 |
Correct |
10 ms |
10368 KB |
Output is correct |
| 8 |
Correct |
12 ms |
10368 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10368 KB |
Output is correct |
| 10 |
Correct |
11 ms |
10496 KB |
Output is correct |
| 11 |
Correct |
133 ms |
38264 KB |
Output is correct |
| 12 |
Correct |
27 ms |
36608 KB |
Output is correct |
| 13 |
Correct |
18 ms |
13696 KB |
Output is correct |
| 14 |
Incorrect |
326 ms |
41476 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
