oj.uz

Submission #581306

# Submission time Handle Problem Language Result Execution time Memory
581306 2022-06-22T12:57:00 Z qwerasdfzxcl Robots (APIO13_robots) C++14
100 / 100
 1053 ms 107796 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[81][505][505];
bool chk[81][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][i][j] = 1e9;
            }
        }
    }
 
 
    //printf("%d %d %d\n", to[2][6][1].x, to[2][6][1].y, to[2][6][1].d);
}
 
 
 
void bfs(int t){
    int l = t/9, r = t%9;
    //printf(" %d %d\n", l, r);
 
    priority_queue<Vertex> pq;
 
    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            if (l==r&& a[i][j]=='1'+l) dist[t][i][j] = 0;
            if (dist[t][i][j]<1e9) pq.emplace(i, j, dist[t][i][j]);
        }
    }
 
 
    queue<pair<int, int>> q;
    while(!pq.empty() || !q.empty()){
 
        if (q.empty()){
            while(!pq.empty()){
                auto [x, y, d] = pq.top(); pq.pop();
                //if (t==21) printf("%d %d %d\n", x, y, d);
                if (chk[t][x][y]) continue;
                assert(d==dist[t][x][y]);
                chk[t][x][y] = 1;
                q.emplace(x, y);
                break;
            }
            continue;
        }
 
        while(!pq.empty()){
            auto [nx, ny] = q.back();
            auto [nx2, ny2, d] = pq.top();
            assert(d>=dist[t][nx][ny]);
 
            if (d!=dist[t][nx][ny]) break;
 
            if (!chk[t][nx2][ny2]){
                q.emplace(nx2, ny2);
                chk[t][nx2][ny2] = 1;
                assert(d==dist[t][nx2][ny2]);
            }
 
            pq.pop();
        }
 
        auto [x, y] = q.front(); q.pop();
        //if (t==21 && dist[t][x][y]==2) printf("YES %d %d\n", x, y);
        for (int i=0;i<l;i++){
            dist[i*9+r][x][y] = min(dist[i*9+r][x][y], dist[i*9+l-1][x][y] + dist[t][x][y]);
        }
      for (int i=r+1;i<n;i++){
            dist[l*9+i][x][y] = min(dist[l*9+i][x][y], dist[l*9+r][x][y] + dist[(r+1)*9+i][x][y]);
        }
 
        for (int d=0;d<4;d++){
            int nx = to[x][y][d].x, ny = to[x][y][d].y;
            //if (!nx) printf("%d %d %d\n", x, y, d);
            assert(nx);
 
 
            if (chk[t][nx][ny]) continue;
 
 
            dist[t][nx][ny] = dist[t][x][y] + 1;
            chk[t][nx][ny] = 1;
            q.emplace(nx, ny);
 
 
 
 
        }
    }
}
 
int main(){
 
    scanf("%d %d %d", &n, &w, &h);
  	if (n==1) {printf("0\n"); exit(0);}
    init();
 
    for (int d=0;d<n-1;d++){
        for (int i=0;i<n-d;i++){
            int j = i+d;
            bfs(i*9+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[21][i][j]!=1e9)printf("%d ", dist[21][i][j]);
            //else printf("x ");
            ans = min(ans, dist[n-1][i][j]);
        }
        //printf("\n");
    }
    printf("%d\n", ans==1e9?-1:ans);
    return 0;
}

Compilation message

robots.cpp: In function 'void bfs(int)':
robots.cpp:81:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |                 auto [x, y, d] = pq.top(); pq.pop();
      |                      ^
robots.cpp:93:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |             auto [nx, ny] = q.back();
      |                  ^
robots.cpp:94:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |             auto [nx2, ny2, d] = pq.top();
      |                  ^
robots.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         auto [x, y] = q.front(); q.pop();
      |              ^
robots.cpp: In function 'void init()':
robots.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%s", a[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     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 980 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 980 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 980 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 980 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 140 ms 61344 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 32 ms 54992 KB Output is correct
14 Correct 374 ms 62296 KB Output is correct
15 Correct 77 ms 57900 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 980 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 980 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 140 ms 61344 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 32 ms 54992 KB Output is correct
14 Correct 374 ms 62296 KB Output is correct
15 Correct 77 ms 57900 KB Output is correct
16 Correct 74 ms 95092 KB Output is correct
17 Correct 1053 ms 107796 KB Output is correct
18 Correct 187 ms 98588 KB Output is correct
19 Correct 70 ms 94624 KB Output is correct
20 Correct 748 ms 107544 KB Output is correct