oj.uz

Submission #122100

# Submission time Handle Problem Language Result Execution time Memory
122100 2019-06-27T14:37:43 Z jakob_nogler Robots (APIO13_robots) C++14
60 / 100
 581 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;
    
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 88 ms 85212 KB Output is correct
2 Correct 82 ms 85172 KB Output is correct
3 Correct 82 ms 85340 KB Output is correct
4 Correct 83 ms 85348 KB Output is correct
5 Correct 85 ms 85368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 85212 KB Output is correct
2 Correct 82 ms 85172 KB Output is correct
3 Correct 82 ms 85340 KB Output is correct
4 Correct 83 ms 85348 KB Output is correct
5 Correct 85 ms 85368 KB Output is correct
6 Correct 84 ms 85288 KB Output is correct
7 Correct 87 ms 85276 KB Output is correct
8 Correct 84 ms 85360 KB Output is correct
9 Correct 84 ms 85212 KB Output is correct
10 Correct 82 ms 85384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 85212 KB Output is correct
2 Correct 82 ms 85172 KB Output is correct
3 Correct 82 ms 85340 KB Output is correct
4 Correct 83 ms 85348 KB Output is correct
5 Correct 85 ms 85368 KB Output is correct
6 Correct 84 ms 85288 KB Output is correct
7 Correct 87 ms 85276 KB Output is correct
8 Correct 84 ms 85360 KB Output is correct
9 Correct 84 ms 85212 KB Output is correct
10 Correct 82 ms 85384 KB Output is correct
11 Correct 315 ms 125808 KB Output is correct
12 Correct 93 ms 88372 KB Output is correct
13 Correct 119 ms 111224 KB Output is correct
14 Correct 581 ms 135348 KB Output is correct
15 Correct 204 ms 125384 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 85212 KB Output is correct
2 Correct 82 ms 85172 KB Output is correct
3 Correct 82 ms 85340 KB Output is correct
4 Correct 83 ms 85348 KB Output is correct
5 Correct 85 ms 85368 KB Output is correct
6 Correct 84 ms 85288 KB Output is correct
7 Correct 87 ms 85276 KB Output is correct
8 Correct 84 ms 85360 KB Output is correct
9 Correct 84 ms 85212 KB Output is correct
10 Correct 82 ms 85384 KB Output is correct
11 Correct 315 ms 125808 KB Output is correct
12 Correct 93 ms 88372 KB Output is correct
13 Correct 119 ms 111224 KB Output is correct
14 Correct 581 ms 135348 KB Output is correct
15 Correct 204 ms 125384 KB Output is correct
16 Runtime error 351 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -