Submission #122075

#	Time	Username	Problem	Language	Result	Execution time	Memory
122075		jakob_nogler	Robots (APIO13_robots)	C++14	30 / 100	147 ms	118948 KiB

robots

    #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[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 = 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];
            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; 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 (stderr)

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

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