oj.uz

Submission #408712

# Submission time Handle Problem Language Result Execution time Memory
408712 2021-05-19T14:19:25 Z Nodir_Bobiev Robots (APIO13_robots) C++17
60 / 100
 1500 ms 71796 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} };

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, priority_queue < vector < int > > q){
    while( !q.empty() ){
        auto fr = q.top(); q.pop();
        int cost = -fr[0], x = fr[1], y = fr[2];
        if( cost != dp[id][x][y] ) continue;
        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({-dp[id][to.x][to.y], to.x, to.y});
            }
        }
    }
}

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;
                    priority_queue < vector < int > > pq;
                    pq.push({0, 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;
            priority_queue < vector < int > > pq;
            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 ) pq.push({-dp[hsh[i][j]][x][y], x, y});
                }
            }
            bfs(hsh[i][j], pq);
        }
    }/*
    for( int d = 0; d < 4; d ++ ){
        cout << "----> " << d << endl;
        for( int i = 0; i < h; i ++ ){
            for( int j = 0; j < w; j ++ ){
                cout << nxt[d][i][j].x << ' ' << nxt[d][i][j].y << "    " ;
            }cout << endl;
        }
    }
    for( int i = 0; i < n; i ++ ){
        for( int j = i+1; j <= n; j ++ ){
            cout << "----> " << i << ' ' << j << endl;
            for( int x = 0; x < h; x ++ ){
                for( int y = 0; y < w; y ++ ){
                    cout << dp[hsh[i][j]][x][y] << ' ';
                }cout << endl;
            }
        }
    }*/
    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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 338 ms 35924 KB Output is correct
12 Correct 16 ms 6476 KB Output is correct
13 Correct 37 ms 22876 KB Output is correct
14 Correct 1328 ms 40164 KB Output is correct
15 Correct 168 ms 34376 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 338 ms 35924 KB Output is correct
12 Correct 16 ms 6476 KB Output is correct
13 Correct 37 ms 22876 KB Output is correct
14 Correct 1328 ms 40164 KB Output is correct
15 Correct 168 ms 34376 KB Output is correct
16 Correct 137 ms 55120 KB Output is correct
17 Execution timed out 1567 ms 71796 KB Time limit exceeded
18 Halted 0 ms 0 KB -