| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 509975 |
2022-01-14T13:04:28 Z |
blue |
Robots (APIO13_robots) |
C++17 |
|
365 ms |
163844 KB |
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using vvi = vector<vi>;
const int fr = 0;
const int lt = 3;
const int rt = 1;
const int bl = 2;
int n, h, w;
int mov[5];
// const int tm
vvi edge;
vvi rev_edge;
void add_edge(int u, int v)
{
edge[u].push_back(v);
rev_edge[v].push_back(u);
}
const int INF = 10'000'000;
vi occ[750'000];
vi* act_edge;
void bfs(vi& dst, int mxd)
{
// cerr <<"bfs called\n";
// bool flg = (mxd==0);
queue<int> tbv;
for(int d = 0; d <= mxd; d++)
{
// cerr << "d = " << d << ", mxd = " << mxd << '\n';
for(int o: occ[d])
{
// cerr << "o = " << o << '\n';
if(dst[o] != d) continue;
tbv.push(o);
}
// cerr << "chk\n";
while((!tbv.empty()) && dst[tbv.front()] == d)
{
int u = tbv.front();
tbv.pop();
// cerr << "Node = " << u << '\n';
for(int v: act_edge[u])
{
// cerr << u << " -> " << v << '\n';
if(dst[v] <= dst[u] + 1) continue;
dst[v] = dst[u] + 1;
tbv.push(v);
mxd = max(mxd, dst[v]);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> w >> h;
vi state((h+2)*(w+2), bl);
int loc[n];
vi actual_ind((h+2)*(w+2), -1);
int ai = 0;
// vi ai;
for(int r = 1; r <= h; r++)
{
for(int c = 1; c <= w; c++)
{
int i = (w+2)*r+c;
char z;
cin >> z;
if('1' <= z && z <= '9')
{
loc[z-'1'] = i;
state[i] = fr;
}
else if(z == '.')
{
state[i] = fr;
}
else if(z == 'A')
{
state[i] = lt;
}
else if(z == 'C')
{
state[i] = rt;
}
else if(z == 'x')
{
state[i] = bl;
}
}
}
mov[0] = -(w+2); //0 = top
mov[1] = +1; //1 = right
mov[2] = +(w+2); //2 = down
mov[3] = -1; //3 = left
mov[4] = 0;
// vi edge[5*(h+2)*(w+2)];
// vi in_edgd
edge = vvi(5*(h+2)*(w+2));
rev_edge = vvi(5*(h+2)*(w+2));
vi dest(5*(h+2)*(w+2), -1);
queue<int> tbv;
for(int r = 1; r <= h; r++)
{
for(int c = 1; c <= w; c++)
{
int i = (w+2)*r + c;
if(state[i] == bl) continue;
ai++;
actual_ind[i] = ai-1;
// cerr << r << ' ' << c << '\n';
for(int dir = 0; dir <= 3; dir++)
{
// cerr << " " << dir << '\n';
add_edge(5*i + 4, 5*i + dir);
// cerr << "A\n";
if(state[i + mov[dir]] != bl)
{
// cerr << "B\n";
add_edge(5*i + dir, 5*(i + mov[dir]) + (dir + state[i + mov[dir]])%4);
// cerr << "C\n";
}
else
{
// cerr << "D\n";
add_edge(5*i + dir, 5*i + 4);
dest[5*i + dir] = i;
tbv.push(5*i + dir);
// cerr << "E\n";
}
}
}
}
// cerr << "A\n";
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
for(int v: rev_edge[u])
{
if(v % 5 == 4) continue;
if(dest[v] != -1) continue;
dest[v] = dest[u];
tbv.push(v);
}
}
act_edge = new vi[(h+2)*(w+2)];
for(int r = 1; r <= h; r++)
{
for(int c = 1; c <= w; c++)
{
int ind = (w+2)*r + c;
for(int q = 0; q < 4; q++)
{
if(dest[5*ind + q] == -1 || dest[5*ind+q] == ind) continue;
act_edge[actual_ind[ind]].push_back(actual_ind[dest[5*ind+q]]);
}
// cerr << "current cell = " << r << ' ' << c << " : ";
// for(int a: act_edge[ind]) cerr << a/(w+2) << " " << a%(w+2) << " | ";
// cerr << '\n';
}
}
// cerr << "B\n";
// for(int f = )
edge.clear();
rev_edge.clear();
dest.clear();
state.clear();
vi dp[n][n];
for(int i = 0; i < n; i++)
{
// cerr << ai << ' ' << actual_ind[loc[i]] << '\n';
occ[0].push_back(actual_ind[loc[i]]);
// cerr << "p\n";
dp[i][i] = vi(ai, INF);
// cerr << "q\n";
dp[i][i][actual_ind[loc[i]]] = 0;
// cerr << "r\n";
bfs(dp[i][i], 0);
occ[0].pop_back();
// cerr << "\n\n\n";
// cerr << "robot = " << i+1 << '\n';
// for(int l = 0; l < (h+2)*(w+2); l++)
// {
// if(dp[i][i][l] >= INF) continue;
// // cerr << l/(w+2) << ' ' << l%(w+2) << " : " << dp[i][i][l] << '\n';
// }
}
// cerr << "C\n";
// cerr << "check\n";
for(int d = 1; d < n; d++)
{
for(int i = 0; i+d < n; i++)
{
int j = i+d;
// cerr << "\n\n\n computing dp " << i << ' ' << j << '\n';
dp[i][j] = vi(ai, INF);
for(int k = i; k < j; k++)
{
for(int x = 0; x < ai; x++)
{
dp[i][j][x] = min(dp[i][j][x], dp[i][k][x] + dp[k+1][j][x]);
}
}
// cerr << "#\n";
vi elim;
// cerr << i << ' ' << j << " pre bfs\n";
for(int u = 0; u < ai; u++)
if(dp[i][j][u] < INF) //add constraint on bfs here?
{
occ[dp[i][j][u]].push_back(u);
elim.push_back(dp[i][j][u]);
}
bfs(dp[i][j], d*h*w);
for(int e: elim) occ[e].clear();
}
}
int final_ans = INF;
for(int u = 0; u < ai; u++)
{
final_ans = min(final_ans, dp[0][n-1][u]);
}
if(final_ans >= INF) final_ans = -1;
cout << final_ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
17848 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 5 |
Correct |
10 ms |
17988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
17848 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 5 |
Correct |
10 ms |
17988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 7 |
Correct |
12 ms |
17872 KB |
Output is correct |
| 8 |
Correct |
11 ms |
17844 KB |
Output is correct |
| 9 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 10 |
Correct |
10 ms |
17868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
17848 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 5 |
Correct |
10 ms |
17988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 7 |
Correct |
12 ms |
17872 KB |
Output is correct |
| 8 |
Correct |
11 ms |
17844 KB |
Output is correct |
| 9 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 10 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 11 |
Correct |
141 ms |
67144 KB |
Output is correct |
| 12 |
Correct |
76 ms |
58520 KB |
Output is correct |
| 13 |
Correct |
108 ms |
64568 KB |
Output is correct |
| 14 |
Correct |
204 ms |
66468 KB |
Output is correct |
| 15 |
Correct |
123 ms |
66252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
17848 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 5 |
Correct |
10 ms |
17988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
17868 KB |
Output is correct |
| 7 |
Correct |
12 ms |
17872 KB |
Output is correct |
| 8 |
Correct |
11 ms |
17844 KB |
Output is correct |
| 9 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 10 |
Correct |
10 ms |
17868 KB |
Output is correct |
| 11 |
Correct |
141 ms |
67144 KB |
Output is correct |
| 12 |
Correct |
76 ms |
58520 KB |
Output is correct |
| 13 |
Correct |
108 ms |
64568 KB |
Output is correct |
| 14 |
Correct |
204 ms |
66468 KB |
Output is correct |
| 15 |
Correct |
123 ms |
66252 KB |
Output is correct |
| 16 |
Runtime error |
365 ms |
163844 KB |
Execution killed with signal 9 |
| 17 |
Halted |
0 ms |
0 KB |
- |
