oj.uz

Submission #122083

# Submission time Handle Problem Language Result Execution time Memory
122083 2019-06-27T14:08:04 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 376 ms 163840 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#pragma optimizer ("O3");
    
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;
typedef tuple<si, si, si, si, si> tiiiii;
    
const int N = 505;
const int dir = 4;
const int R = 9;
const int inf = 10e8;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][N][N];
bool vis0[N][N][dir];
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[300 * 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});
    }
    
    set<tiiiii> s;
    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 < 300 * 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;
}

Compilation message

robots.cpp:4:0: warning: ignoring #pragma optimizer  [-Wunknown-pragmas]
 #pragma optimizer ("O3");

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 102524 KB Output is correct
2 Correct 105 ms 102392 KB Output is correct
3 Correct 108 ms 102404 KB Output is correct
4 Correct 111 ms 102520 KB Output is correct
5 Correct 106 ms 102616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 102524 KB Output is correct
2 Correct 105 ms 102392 KB Output is correct
3 Correct 108 ms 102404 KB Output is correct
4 Correct 111 ms 102520 KB Output is correct
5 Correct 106 ms 102616 KB Output is correct
6 Correct 107 ms 102464 KB Output is correct
7 Correct 100 ms 102392 KB Output is correct
8 Correct 103 ms 102492 KB Output is correct
9 Correct 109 ms 102496 KB Output is correct
10 Correct 105 ms 102588 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 102524 KB Output is correct
2 Correct 105 ms 102392 KB Output is correct
3 Correct 108 ms 102404 KB Output is correct
4 Correct 111 ms 102520 KB Output is correct
5 Correct 106 ms 102616 KB Output is correct
6 Correct 107 ms 102464 KB Output is correct
7 Correct 100 ms 102392 KB Output is correct
8 Correct 103 ms 102492 KB Output is correct
9 Correct 109 ms 102496 KB Output is correct
10 Correct 105 ms 102588 KB Output is correct
11 Correct 359 ms 159792 KB Output is correct
12 Correct 120 ms 106632 KB Output is correct
13 Correct 180 ms 139004 KB Output is correct
14 Runtime error 376 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 105 ms 102524 KB Output is correct
2 Correct 105 ms 102392 KB Output is correct
3 Correct 108 ms 102404 KB Output is correct
4 Correct 111 ms 102520 KB Output is correct
5 Correct 106 ms 102616 KB Output is correct
6 Correct 107 ms 102464 KB Output is correct
7 Correct 100 ms 102392 KB Output is correct
8 Correct 103 ms 102492 KB Output is correct
9 Correct 109 ms 102496 KB Output is correct
10 Correct 105 ms 102588 KB Output is correct
11 Correct 359 ms 159792 KB Output is correct
12 Correct 120 ms 106632 KB Output is correct
13 Correct 180 ms 139004 KB Output is correct
14 Runtime error 376 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -