oj.uz

Submission #408747

# Submission time Handle Problem Language Result Execution time Memory
408747 2021-05-19T15:15:59 Z Nodir_Bobiev Robots (APIO13_robots) C++17
100 / 100
 527 ms 98888 KB 
/* In the name of Allah */
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int inf = 1000000;
int n, w, h;
string grid[510];
int hsh[10][10], dp[50][510][510];
bool vis[4][510][510];
pair < int, int > nxt[4][510][510];
pair < int, int > dirs[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };
vector < pair < int, int > > locs[inf];

bool ok( int x, int y ){
    return( 0 <= x && x < h && 0 <= y && y < w && grid[x][y] != 'x');
}

/*
nxt[d][x][y] = {-1, -1} -> nxt[d][x][y] is not calculated yet;
nxt[d][x][y] = {-2, -2} -> nxt[d][x][y] is not defined. There are a infinite loop;
nxt[d][x][y] is not in {{-2, -2} {-1, -1}} -> nxt[d][x][y] is calculated.
*/

pair < int, int > rec(int d, int x, int y){
    if( nxt[d][x][y] != make_pair(-1, -1) )return nxt[d][x][y];
    if( vis[d][x][y] ) return nxt[d][x][y] = {-2, -2};
    vis[d][x][y] = 1;
    int dd = d;
    if( grid[x][y] == 'A' )if( --dd < 0 ) dd += 4;
    if( grid[x][y] == 'C' )if( ++dd > 3 ) dd -= 4;

    int xx = x + dirs[dd].x, yy = y + dirs[dd].y;
    if( ok(xx, yy) ) return nxt[d][x][y] = rec( dd, xx, yy );
    return nxt[d][x][y] = {x,y};
}

void bfs( int id, queue < pair < int, int > > q){
    while( !q.empty() ){
        auto fr = q.front(); q.pop();
        int x = fr.x, y = fr.y;
        int c = dp[id][x][y];
        for( int d = 0; d < 4; d ++ ){
            auto to = nxt[d][x][y];
            if( to != make_pair(-2, -2) && dp[id][x][y] + 1 < dp[id][to.x][to.y] ){
                dp[id][to.x][to.y] = dp[id][x][y] + 1;
                q.push({to.x, to.y});
            }
        }
        if( !locs[c+1].empty() ){
            for( auto pr: locs[c+1] ){
                if( dp[id][pr.x][pr.y] == c+1 )
                    q.push(pr);
            }
            locs[c+1].clear();
        }
    }
}

int main(){
    cin >> n >> w >> h;
    for( int i = 0; i < h; i ++ )
        cin >> grid[i];

    int cnt = 0;
    for( int i = 0; i < n; i ++ ){
        for( int j = i+1; j <= n; j ++ ){
            hsh[i][j] = cnt++;
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int d = 0; d < 4; d ++ ){
                nxt[d][i][j] = {-1, -1};
            }
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int d = 0; d < 4; d ++ ){
                rec(d, i, j);
            }
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int id = 0; id < cnt; id ++ ){
                dp[id][i][j] = inf;
            }
        }
    }
    for( int id = 0; id < n; id ++ ){
        for( int i = 0; i < h; i ++ ){
            for( int j= 0; j < w; j ++ ){
                if( grid[i][j] == id + 49 ){
                    dp[hsh[id][id+1]][i][j] = 0;
                    queue < pair < int, int > > pq;
                    pq.push({i, j} );
                    bfs(hsh[id][id+1], pq);
                }
            }
        }
    }
    for( int len = 2; len <= n ; len ++ ){
        for( int i = 0; i <= n - len; i ++ ){
            int j = i + len, mn = inf;
            vector < int > used;
            for( int x = 0; x < h; x ++ ){
                for( int y = 0; y < w; y ++ ){
                    for( int k = i+1; k < j; k ++ ){
                        if( dp[hsh[i][j]][x][y] > dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y] ){
                            dp[hsh[i][j]][x][y] = dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y];
                        }
                    }
                    if( dp[hsh[i][j]][x][y] != inf ){
                        locs[dp[hsh[i][j]][x][y]].push_back({x,y});
                        used.push_back({dp[hsh[i][j]][x][y]});
                        mn = min( mn, dp[hsh[i][j]][x][y] );
                    }
                }
            }
            queue < pair < int, int > > pq;
            for( auto pr: locs[mn] )
                pq.push(pr);
            bfs(hsh[i][j], pq);
            for( auto c: used ) locs[c].clear();
        }
    }
    int res = inf;
    for( int x = 0; x < h; x ++ ){
        for( int y = 0; y < w; y ++ ){
            res = min( res, dp[hsh[0][n]][x][y] );
        }
    }
    if( res == inf ) cout << -1;
    else cout << res;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23748 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 15 ms 24012 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23748 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 15 ms 24012 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 13 ms 24052 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23748 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 15 ms 24012 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 13 ms 24052 KB Output is correct
11 Correct 109 ms 59984 KB Output is correct
12 Correct 25 ms 30028 KB Output is correct
13 Correct 48 ms 46472 KB Output is correct
14 Correct 196 ms 62596 KB Output is correct
15 Correct 83 ms 57544 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23748 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 15 ms 24012 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 13 ms 24052 KB Output is correct
11 Correct 109 ms 59984 KB Output is correct
12 Correct 25 ms 30028 KB Output is correct
13 Correct 48 ms 46472 KB Output is correct
14 Correct 196 ms 62596 KB Output is correct
15 Correct 83 ms 57544 KB Output is correct
16 Correct 156 ms 78644 KB Output is correct
17 Correct 527 ms 98888 KB Output is correct
18 Correct 188 ms 82116 KB Output is correct
19 Correct 161 ms 78604 KB Output is correct
20 Correct 392 ms 92776 KB Output is correct