oj.uz

Submission #122414

# Submission time Handle Problem Language Result Execution time Memory
122414 2019-06-28T07:20:52 Z jakob_nogler Robots (APIO13_robots) C++14
60 / 100
 548 ms 163840 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
    
using namespace std;
    
typedef short int si;
typedef pair<si, si> pii;
typedef tuple<si, si, si> tiii;
typedef tuple<si, si, si, si> tiiii;
    
const int N = 355, dir = 4, R = 9, inf = 10e8, sum = R * (R + 1) / 2;
const int lim = N * N * 2 / 5;

pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
char grid[N][N];
int n, w, h;
    
int dr[dir] = {1, 0, - 1, 0};
int dc[dir] = {0, 1, 0, - 1}; //down, right, up, left
    
queue<tiiii> q3[N * N];
    
int main(){
    cin >> n >> w >> h;
    w += 2; h += 2;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            grid[i][j] = 'x';
            for(int k = 0; k < dir; k++)
                nxt[i][j][k] = {- 1, - 1};
            for(int k = 0; k < n; k++)
                cost[k][i][j] = - 1;
            for(int k = 0; k < sum; k++)
                dp[k][i][j] = inf;
        }
    
    int idx = 0;
    for(int i = 0; i < R; i++)
        for(int j = i; j < R; j++)
            dict[i][j] = idx++;
    
    queue<tiii> q0, q1;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++){
            cin >> grid[i][j];
            if(grid[i][j] >= '1' && grid[i][j] <= '9'){
                cost[grid[i][j] - '1'][i][j] = 0;
                q1.push({grid[i][j] - '1', i, j});
            }
        }
    
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            for(int k = 0; k < dir; k++)
                if(grid[i][j] != 'x' && grid[i + dr[k]][j + dc[k]] == 'x'){
                    q0.push({i, j, k});
                    nxt[i][j][k] = {i, j};
                }
    
    while(!q0.empty()){
        tiii curr = q0.front();
        q0.pop();
        int d = get<2>(curr), id, mov;
        pii pos = {get<0>(curr), get<1>(curr)};
    
        if(grid[pos.fi][pos.se] == 'A') mov = (d + 1) % 4, id = (d + 3) % 4;
        else if(grid[pos.fi][pos.se] == 'C') mov = (d + 3) % 4, id = (d + 1) % 4;
        else mov = (d + 2) % 4, id = d;
        if(grid[pos.fi + dr[mov]][pos.se + dc[mov]] == 'x') continue;
        nxt[pos.fi + dr[mov]][pos.se + dc[mov]][id] = nxt[pos.fi][pos.se][d];
        q0.push({pos.fi + dr[mov], pos.se + dc[mov], id});
    }
    
    while(!q1.empty()){
        tiii curr = q1.front();
        q1.pop();
        int r = get<0>(curr);
        pii pos = {get<1>(curr), get<2>(curr)};
    
        dp[dict[r][r]][pos.fi][pos.se] = cost[r][pos.fi][pos.se];
        q3[cost[r][pos.fi][pos.se]].push({r, r, pos.fi, pos.se});
    
        for(int i = 0; i < dir; i++){
            pii nn = nxt[pos.fi][pos.se][i];
            if(cost[r][nn.fi][nn.se] == - 1){
                cost[r][nn.fi][nn.se] = cost[r][pos.fi][pos.se] + 1;
                q1.push({r, nn.fi, nn.se});
            }
        }
    }
    
    for(int v = 0; v < N * N; v++){
        while(!q3[v].empty()){
            tiiii curr = q3[v].front();
            q3[v].pop();
    
            int lo = get<0>(curr), hi = get<1>(curr);
            pii pos = {get<2>(curr), get<3>(curr)};
    
            if(lo == 0 && hi == n - 1){
                cout << v << endl;
                return 0;
            }
    
            if(dp[dict[lo][hi]][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[dict[lo][i]][pos.fi][pos.se] > dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    int val = dp[dict[lo][i]][pos.fi][pos.se] = dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    if(val < lim) q3[dp[dict[lo][i]][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[dict[i][hi]][pos.fi][pos.se] > dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    int val = dp[dict[i][hi]][pos.fi][pos.se] = dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    if(val < lim) q3[dp[dict[i][hi]][pos.fi][pos.se]].push({i, hi, pos.fi, pos.se});
                }
    
            for(int i = 0; i < dir; i++){
                pii nn = nxt[pos.fi][pos.se][i];
                if(dp[dict[lo][hi]][nn.fi][nn.se] > dp[dict[lo][hi]][pos.fi][pos.se] + 1){
                    int val = dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
                    if(val < lim) q3[dp[dict[lo][hi]][nn.fi][nn.se]].push({lo, hi, nn.fi, nn.se});
                }
            }
        }
    }
    
    int ans = inf;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            ans = min(ans, dp[dict[0][n - 1]][i][j]);
    
    if(ans == inf) cout << - 1 << endl;
    else cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 85496 KB Output is correct
2 Correct 92 ms 85496 KB Output is correct
3 Correct 79 ms 85496 KB Output is correct
4 Correct 92 ms 86264 KB Output is correct
5 Correct 87 ms 86140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 85496 KB Output is correct
2 Correct 92 ms 85496 KB Output is correct
3 Correct 79 ms 85496 KB Output is correct
4 Correct 92 ms 86264 KB Output is correct
5 Correct 87 ms 86140 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 79 ms 85484 KB Output is correct
8 Correct 79 ms 85752 KB Output is correct
9 Correct 81 ms 85620 KB Output is correct
10 Correct 81 ms 86136 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 85496 KB Output is correct
2 Correct 92 ms 85496 KB Output is correct
3 Correct 79 ms 85496 KB Output is correct
4 Correct 92 ms 86264 KB Output is correct
5 Correct 87 ms 86140 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 79 ms 85484 KB Output is correct
8 Correct 79 ms 85752 KB Output is correct
9 Correct 81 ms 85620 KB Output is correct
10 Correct 81 ms 86136 KB Output is correct
11 Correct 290 ms 110684 KB Output is correct
12 Correct 111 ms 106872 KB Output is correct
13 Correct 112 ms 109528 KB Output is correct
14 Correct 548 ms 119500 KB Output is correct
15 Correct 187 ms 110200 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 85496 KB Output is correct
2 Correct 92 ms 85496 KB Output is correct
3 Correct 79 ms 85496 KB Output is correct
4 Correct 92 ms 86264 KB Output is correct
5 Correct 87 ms 86140 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 79 ms 85484 KB Output is correct
8 Correct 79 ms 85752 KB Output is correct
9 Correct 81 ms 85620 KB Output is correct
10 Correct 81 ms 86136 KB Output is correct
11 Correct 290 ms 110684 KB Output is correct
12 Correct 111 ms 106872 KB Output is correct
13 Correct 112 ms 109528 KB Output is correct
14 Correct 548 ms 119500 KB Output is correct
15 Correct 187 ms 110200 KB Output is correct
16 Runtime error 255 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -