oj.uz

Submission #122064

# Submission time Handle Problem Language Result Execution time Memory
122064 2019-06-27T13:37:04 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 1500 ms 110940 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#pragma optimizer ("O3");

using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
typedef tuple<int, int, int, int, int> 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

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 = 0; i < h; i++){
        for(int j = 0; j < w; j++)
            cout << grid[i][j] << " ";
        cout << endl;
    }*/

    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];
        s.insert({cost[r][pos.fi][pos.se], 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(!s.empty()){
        tiiiii curr = *s.begin();
        s.erase(s.begin());

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

        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]){
                s.erase({dp[lo][i][pos.fi][pos.se], lo, i, 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];
                s.insert({dp[lo][i][pos.fi][pos.se], 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]){
                s.erase({dp[i][hi][pos.fi][pos.se], i, 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];
                s.insert({dp[i][hi][pos.fi][pos.se], 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){
                s.erase({dp[lo][hi][nn.fi][nn.se], lo, hi, nn.fi, nn.se});
                dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
                s.insert({dp[lo][hi][nn.fi][nn.se], 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 640 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 1262 ms 81124 KB Output is correct
12 Correct 22 ms 7516 KB Output is correct
13 Correct 53 ms 39288 KB Output is correct
14 Execution timed out 1577 ms 110940 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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 1262 ms 81124 KB Output is correct
12 Correct 22 ms 7516 KB Output is correct
13 Correct 53 ms 39288 KB Output is correct
14 Execution timed out 1577 ms 110940 KB Time limit exceeded
15 Halted 0 ms 0 KB -