Submission #581306

#	Time	Username	Problem	Language	Result	Execution time	Memory
581306		qwerasdfzxcl	Robots (APIO13_robots)	C++14	100 / 100	1053 ms	107796 KiB

robots

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40