oj.uz

Submission #122086

# Submission time Handle Problem Language Result Execution time Memory
122086 2019-06-27T14:13:30 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 442 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 = 405, dir = 4, R = 9, inf = 10e8;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][N][N];
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 < n; k++)
                for(int l = 0; l < n; l++)
                    dp[k][l][i][j] = inf;
        }
    
    
    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[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(dp[lo][hi][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[lo][i][pos.fi][pos.se] > dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[lo][i][pos.fi][pos.se] = dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[lo][i][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[i][hi][pos.fi][pos.se] > dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[i][hi][pos.fi][pos.se] = dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[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[lo][hi][nn.fi][nn.se] > dp[lo][hi][pos.fi][pos.se] + 1){
                    dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
                    q3[dp[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[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 104 ms 110840 KB Output is correct
2 Correct 108 ms 110968 KB Output is correct
3 Correct 117 ms 110840 KB Output is correct
4 Correct 111 ms 110940 KB Output is correct
5 Correct 109 ms 110928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 110840 KB Output is correct
2 Correct 108 ms 110968 KB Output is correct
3 Correct 117 ms 110840 KB Output is correct
4 Correct 111 ms 110940 KB Output is correct
5 Correct 109 ms 110928 KB Output is correct
6 Correct 103 ms 110840 KB Output is correct
7 Correct 123 ms 110836 KB Output is correct
8 Correct 107 ms 110984 KB Output is correct
9 Correct 122 ms 110820 KB Output is correct
10 Correct 111 ms 110968 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 110840 KB Output is correct
2 Correct 108 ms 110968 KB Output is correct
3 Correct 117 ms 110840 KB Output is correct
4 Correct 111 ms 110940 KB Output is correct
5 Correct 109 ms 110928 KB Output is correct
6 Correct 103 ms 110840 KB Output is correct
7 Correct 123 ms 110836 KB Output is correct
8 Correct 107 ms 110984 KB Output is correct
9 Correct 122 ms 110820 KB Output is correct
10 Correct 111 ms 110968 KB Output is correct
11 Correct 328 ms 156832 KB Output is correct
12 Correct 157 ms 114336 KB Output is correct
13 Correct 154 ms 140508 KB Output is correct
14 Runtime error 442 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 110840 KB Output is correct
2 Correct 108 ms 110968 KB Output is correct
3 Correct 117 ms 110840 KB Output is correct
4 Correct 111 ms 110940 KB Output is correct
5 Correct 109 ms 110928 KB Output is correct
6 Correct 103 ms 110840 KB Output is correct
7 Correct 123 ms 110836 KB Output is correct
8 Correct 107 ms 110984 KB Output is correct
9 Correct 122 ms 110820 KB Output is correct
10 Correct 111 ms 110968 KB Output is correct
11 Correct 328 ms 156832 KB Output is correct
12 Correct 157 ms 114336 KB Output is correct
13 Correct 154 ms 140508 KB Output is correct
14 Runtime error 442 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -