Submission #581306

#TimeUsernameProblemLanguageResultExecution timeMemory
581306qwerasdfzxclRobots (APIO13_robots)C++14
100 / 100
1053 ms107796 KiB
#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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...