oj.uz

Submission #122078

# Submission time Handle Problem Language Result Execution time Memory
122078 2019-06-27T14:04:09 Z jakob_nogler Robots (APIO13_robots) C++14
30 / 100
 350 ms 163840 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> tiiii;
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
    
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 104 ms 102484 KB Output is correct
2 Correct 96 ms 102392 KB Output is correct
3 Correct 116 ms 102392 KB Output is correct
4 Correct 98 ms 102520 KB Output is correct
5 Correct 96 ms 102520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 102484 KB Output is correct
2 Correct 96 ms 102392 KB Output is correct
3 Correct 116 ms 102392 KB Output is correct
4 Correct 98 ms 102520 KB Output is correct
5 Correct 96 ms 102520 KB Output is correct
6 Correct 97 ms 102392 KB Output is correct
7 Correct 101 ms 102520 KB Output is correct
8 Correct 115 ms 102424 KB Output is correct
9 Correct 96 ms 102392 KB Output is correct
10 Correct 97 ms 102520 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 102484 KB Output is correct
2 Correct 96 ms 102392 KB Output is correct
3 Correct 116 ms 102392 KB Output is correct
4 Correct 98 ms 102520 KB Output is correct
5 Correct 96 ms 102520 KB Output is correct
6 Correct 97 ms 102392 KB Output is correct
7 Correct 101 ms 102520 KB Output is correct
8 Correct 115 ms 102424 KB Output is correct
9 Correct 96 ms 102392 KB Output is correct
10 Correct 97 ms 102520 KB Output is correct
11 Correct 350 ms 162132 KB Output is correct
12 Correct 131 ms 108664 KB Output is correct
13 Correct 142 ms 141256 KB Output is correct
14 Runtime error 185 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 104 ms 102484 KB Output is correct
2 Correct 96 ms 102392 KB Output is correct
3 Correct 116 ms 102392 KB Output is correct
4 Correct 98 ms 102520 KB Output is correct
5 Correct 96 ms 102520 KB Output is correct
6 Correct 97 ms 102392 KB Output is correct
7 Correct 101 ms 102520 KB Output is correct
8 Correct 115 ms 102424 KB Output is correct
9 Correct 96 ms 102392 KB Output is correct
10 Correct 97 ms 102520 KB Output is correct
11 Correct 350 ms 162132 KB Output is correct
12 Correct 131 ms 108664 KB Output is correct
13 Correct 142 ms 141256 KB Output is correct
14 Runtime error 185 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -