Submission #122074

#	Time	Username	Problem	Language	Result	Execution time	Memory
122074		jakob_nogler	Robots (APIO13_robots)	C++14	30 / 100	1554 ms	75600 KiB

robots

#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, si> tiiiii;
    
const int N = 505, dir = 4, R = 9, inf = 10e8;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][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
    
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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40