oj.uz

Submission #973438

# Submission time Handle Problem Language Result Execution time Memory
973438 2024-05-02T02:26:11 Z socpite Robots (APIO13_robots) C++14
100 / 100
 422 ms 86816 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int INF = 1e9;

int dp[9][9][505*505];
pii val[505][505][4];
int vis[505][505][4];
char board[505][505];
const pii mv[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int n, w, h;

pii add(pii a, pii b){ // ????
    return make_pair(a.first + b.first, a.second + b.second);
}

bool check_wall(pii pos){
    return board[pos.first][pos.second] == 'x' || board[pos.first][pos.second] == 'A' || board[pos.first][pos.second] == 'C';
} 

vector<int> g[505*505];

pii dfs(pii pos, int d){
    if(val[pos.first][pos.second][d].first)return val[pos.first][pos.second][d];
    if(vis[pos.first][pos.second][d]){
        assert(false);
        val[pos.first][pos.second][d] = {-1, -1};
        return {-1, -1};
    }
    vis[pos.first][pos.second][d] = 1;
    auto old_pos = pos;
    pos = add(pos, mv[d]);
    while(!check_wall(pos))pos = add(pos, mv[d]);
    if(board[pos.first][pos.second] == 'x')val[old_pos.first][old_pos.second][d] = add(pos, mv[d^2]);
    else if(board[pos.first][pos.second] == 'C'){
        val[old_pos.first][old_pos.second][d] = dfs(pos, d == 3 ? 0 : d + 1);
    }
    else {
        val[old_pos.first][old_pos.second][d] = dfs(pos, d == 0 ? 3 : d - 1);
    }
    return val[old_pos.first][old_pos.second][d];
    vis[old_pos.first][old_pos.second][d] = 0;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> h >> w;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            for(int k = 0; k < w*h; k++)dp[i][j][k] = INF;
        }
    }
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            cin >> board[i][j];
            if(board[i][j] >= '1' && board[i][j] <= '9')dp[board[i][j] - '1'][board[i][j]-'1'][(i-1)*h + (j-1)] = 0;
            board[0][j] = board[w+1][j] = board[i][0] = board[i][h+1] = 'x';
        }
    }
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            if(board[i][j] == 'x')continue;
            for(int k = 0; k < 4; k++){
                pair<int, int> tmp = dfs(make_pair(i, j), k);
                if(tmp.first != -1){
                    g[(i-1)*h + j - 1].push_back((tmp.first-1)*h + tmp.second - 1);
                }
            }
        }
    }
    for(int len = 0; len < n; len++){
        for(int l = 0; l + len < n; l++){
            int r = l + len;
            vector<pair<int, int>> inital;
            for(int i = 0; i < w*h; i++){
                for(int k = l; k < r; k++){
                    dp[l][r][i] = min(dp[l][r][i], dp[l][k][i] + dp[k+1][r][i]);
                }
                if(dp[l][r][i] < INF)inital.push_back({dp[l][r][i], i});
            }
            sort(inital.rbegin(), inital.rend());
            queue<pair<int, int>> q;
            while(!q.empty() || !inital.empty()){
                pair<int, int> ele;
                if(q.empty() || (!inital.empty() && inital.back().first < q.front().first)){
                    ele = inital.back();
                    inital.pop_back();
                }
                else {
                    ele = q.front();
                    q.pop();
                }
                if(len == n-1){
                    cout << ele.first+1-1;
                    return 0;
                }
                if(ele.first > dp[l][r][ele.second])continue;
                // cout << l << " " << r << " " << ele.second << " " << dp[l][r][ele.second] << endl;
                for(auto v: g[ele.second]){
                    if(dp[l][r][v] > ele.first + 1){
                        dp[l][r][v] = ele.first+1;
                        q.push({ele.first+1, v});
                    }
                }
            }
            if(len == n-1){
                cout << "-1";
                return 0;
            }
        }
    }
    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12940 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12940 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 80 ms 71252 KB Output is correct
12 Correct 11 ms 15476 KB Output is correct
13 Correct 35 ms 53332 KB Output is correct
14 Correct 145 ms 71808 KB Output is correct
15 Correct 39 ms 71184 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12940 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 80 ms 71252 KB Output is correct
12 Correct 11 ms 15476 KB Output is correct
13 Correct 35 ms 53332 KB Output is correct
14 Correct 145 ms 71808 KB Output is correct
15 Correct 39 ms 71184 KB Output is correct
16 Correct 209 ms 86816 KB Output is correct
17 Correct 422 ms 83468 KB Output is correct
18 Correct 90 ms 82320 KB Output is correct
19 Correct 151 ms 82872 KB Output is correct
20 Correct 266 ms 83012 KB Output is correct