oj.uz

Submission #122412

# Submission time Handle Problem Language Result Execution time Memory
122412 2019-06-28T07:20:12 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 509 ms 116472 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 / 3;

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 85 ms 85496 KB Output is correct
2 Correct 83 ms 85580 KB Output is correct
3 Correct 87 ms 85568 KB Output is correct
4 Correct 79 ms 86120 KB Output is correct
5 Correct 99 ms 86216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 85496 KB Output is correct
2 Correct 83 ms 85580 KB Output is correct
3 Correct 87 ms 85568 KB Output is correct
4 Correct 79 ms 86120 KB Output is correct
5 Correct 99 ms 86216 KB Output is correct
6 Correct 90 ms 85600 KB Output is correct
7 Correct 89 ms 85496 KB Output is correct
8 Correct 88 ms 85656 KB Output is correct
9 Correct 81 ms 85624 KB Output is correct
10 Correct 84 ms 86136 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 85496 KB Output is correct
2 Correct 83 ms 85580 KB Output is correct
3 Correct 87 ms 85568 KB Output is correct
4 Correct 79 ms 86120 KB Output is correct
5 Correct 99 ms 86216 KB Output is correct
6 Correct 90 ms 85600 KB Output is correct
7 Correct 89 ms 85496 KB Output is correct
8 Correct 88 ms 85656 KB Output is correct
9 Correct 81 ms 85624 KB Output is correct
10 Correct 84 ms 86136 KB Output is correct
11 Correct 284 ms 110692 KB Output is correct
12 Correct 126 ms 107000 KB Output is correct
13 Correct 119 ms 109636 KB Output is correct
14 Incorrect 509 ms 116472 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 85496 KB Output is correct
2 Correct 83 ms 85580 KB Output is correct
3 Correct 87 ms 85568 KB Output is correct
4 Correct 79 ms 86120 KB Output is correct
5 Correct 99 ms 86216 KB Output is correct
6 Correct 90 ms 85600 KB Output is correct
7 Correct 89 ms 85496 KB Output is correct
8 Correct 88 ms 85656 KB Output is correct
9 Correct 81 ms 85624 KB Output is correct
10 Correct 84 ms 86136 KB Output is correct
11 Correct 284 ms 110692 KB Output is correct
12 Correct 126 ms 107000 KB Output is correct
13 Correct 119 ms 109636 KB Output is correct
14 Incorrect 509 ms 116472 KB Output isn't correct
15 Halted 0 ms 0 KB -