oj.uz

Submission #122141

# Submission time Handle Problem Language Result Execution time Memory
122141 2019-06-27T16:47:22 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 1500 ms 38396 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;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
bool vis[sum][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;
    
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];
        vis[dict[r][r]][pos.fi][pos.se] = true;
        q3.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});
            }
        }
    }

    while(!q3.empty()){
        tiiii curr = q3.front();
        q3.pop();

        int lo = get<0>(curr), hi = get<1>(curr);
        pii pos = {get<2>(curr), get<3>(curr)};

        vis[dict[lo][hi]][pos.fi][pos.se] = false;
        
        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]){
                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(!vis[dict[lo][i]][pos.fi][pos.se]){
                     q3.push({lo, i, pos.fi, pos.se});
                     vis[dict[lo][i]][pos.fi][pos.se] = true;
                }
            }
        
        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]){
                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(!vis[dict[i][hi]][pos.fi][pos.se]){
                    q3.push({i, hi, pos.fi, pos.se});
                    vis[dict[i][hi]][pos.fi][pos.se] = true;
                }
            }

        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){
                dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
                if(!vis[dict[lo][hi]][nn.fi][nn.se]){
                    q3.push({lo, hi, nn.fi, nn.se});
                    vis[dict[lo][hi]][nn.fi][nn.se] = true;
                }
            }
        }
    }
    
    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 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 147 ms 32912 KB Output is correct
12 Correct 34 ms 22136 KB Output is correct
13 Correct 36 ms 24984 KB Output is correct
14 Execution timed out 1581 ms 38396 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 147 ms 32912 KB Output is correct
12 Correct 34 ms 22136 KB Output is correct
13 Correct 36 ms 24984 KB Output is correct
14 Execution timed out 1581 ms 38396 KB Time limit exceeded
15 Halted 0 ms 0 KB -