oj.uz

Submission #581292

# Submission time Handle Problem Language Result Execution time Memory
581292 2022-06-22T12:51:59 Z qwerasdfzxcl Robots (APIO13_robots) C++14
100 / 100
 1439 ms 96996 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Vertex{
    int x, y, d;
    Vertex(){}
    Vertex(int _x, int _y, int _d): x(_x), y(_y), d(_d) {}
    bool operator<(const Vertex &V) const{
        return d > V.d;
    }
}to[505][505][4];
char a[505][505];
bool visited[505][505][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, w, h;

int dist[9][9][505][505];

void dfs(int x, int y, int d){
    visited[x][y][d] = 1;
    int nx, ny, nd = d;
    if (a[x][y]=='A') nd = (d+3)%4;
    if (a[x][y]=='C') nd = (d+1)%4;
    nx = x + dx[nd], ny = y + dy[nd];

    if (a[nx][ny]=='x') to[x][y][d] = Vertex(x, y, d);
    else if (visited[nx][ny][nd]) to[x][y][d] = to[nx][ny][nd];
    else{
        dfs(nx, ny, nd);
        to[x][y][d] = to[nx][ny][nd];
    }
}

void init(){
    for (int i=0;i<=h+1;i++) fill(a[i], a[i]+w+2, 'x');
    for (int i=1;i<=h;i++){
        scanf("%s", a[i]+1);
        a[i][w+1] = 'x';
    }

    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            for (int d=0;d<4;d++) if (!visited[i][j][d]) dfs(i, j, d);
        }
    }

    for (int t=0;t<81;t++){
        for (int i=1;i<=h;i++){
            for (int j=1;j<=w;j++){
                dist[t/9][t%9][i][j] = 1e9;
            }
        }
    }


    //printf("%d %d %d\n", to[1][1][0].x, to[1][1][0].y, to[1][1][0].d);
}



void bfs(int l, int r){
    //printf(" %d %d\n", l, r);

    priority_queue<Vertex> pq;

    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            for (int mid=l;mid+1<=r;mid++){
                dist[l][r][i][j] = min(dist[l][r][i][j], dist[l][mid][i][j] + dist[mid+1][r][i][j]);
            }
            if (l==r && a[i][j]=='1'+l) dist[l][r][i][j] = 0;
            if (dist[l][r][i][j]<1e9) pq.emplace(i, j, dist[l][r][i][j]);
        }
    }


    while(!pq.empty()){
        auto [x, y, dd] = pq.top(); pq.pop();
        if (dd!=dist[l][r][x][y]) continue;
        //if (t==21 && dist[l][r][x][y]==2) printf("YES %d %d\n", x, y);

        for (int d=0;d<4;d++){
            int nx = to[x][y][d].x, ny = to[x][y][d].y;
            if (!nx) continue;
            if (dist[l][r][nx][ny] <= dist[l][r][x][y] + 1) continue;

            dist[l][r][nx][ny] = dist[l][r][x][y] + 1;
            pq.emplace(nx, ny, dist[l][r][nx][ny]);

        }
    }
}

int main(){

    scanf("%d %d %d", &n, &w, &h);
    init();

    for (int d=0;d<n;d++){
        for (int i=0;i<n-d;i++){
            int j = i+d;
            bfs(i, j);
        }
    }
    int ans = 1e9;
    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            //if (dist[0][i][j]==0 && dist[1][i][j]==0) printf("%d %d\n", i, j);
            //if (dist[2][3][i][j]!=1e9)printf("%d ", dist[2][3][i][j]);
            //else printf("x ");
            ans = min(ans, dist[0][n-1][i][j]);
        }
        //printf("\n");
    }
    printf("%d\n", ans==1e9?-1:ans);
    return 0;
}

Compilation message

robots.cpp: In function 'void bfs(int, int)':
robots.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         auto [x, y, dd] = pq.top(); pq.pop();
      |              ^
robots.cpp: In function 'void init()':
robots.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%s", a[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d %d %d", &n, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 140 ms 55060 KB Output is correct
12 Correct 37 ms 54376 KB Output is correct
13 Correct 56 ms 54860 KB Output is correct
14 Correct 479 ms 55876 KB Output is correct
15 Correct 106 ms 54844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 140 ms 55060 KB Output is correct
12 Correct 37 ms 54376 KB Output is correct
13 Correct 56 ms 54860 KB Output is correct
14 Correct 479 ms 55876 KB Output is correct
15 Correct 106 ms 54844 KB Output is correct
16 Correct 138 ms 94040 KB Output is correct
17 Correct 1439 ms 96996 KB Output is correct
18 Correct 196 ms 95508 KB Output is correct
19 Correct 135 ms 94032 KB Output is correct
20 Correct 785 ms 96600 KB Output is correct