Submission #552377

#TimeUsernameProblemLanguageResultExecution timeMemory
552377QwertyPiRobots (APIO13_robots)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back using namespace std; typedef pair<int, int> pii; const int MAXN = 500, MAXM = 500, MAXD = 9; const int INF = (1 << 25); char board[MAXN][MAXM]; int dp[MAXN][MAXM][MAXD][MAXD]; int dd[MAXN][MAXM]; pii f[MAXN][MAXM][4]; pii pos[MAXD]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, -1, 0, 1}; int d, n, m; bool in(int i, int j){ return 0 <= i && i < n && 0 <= j && j < m && board[i][j] != 'x'; } bool vis[MAXN][MAXM][4]; pii dfs(int i, int j, int dir){ if(vis[i][j][dir]) return {-1, -1}; if(f[i][j][dir].fi != -2) return f[i][j][dir]; vis[i][j][dir] = true; if(!in(i + dx[dir], j + dy[dir])){ f[i][j][dir] = {i, j}; vis[i][j][dir] = false; return {i, j}; } f[i][j][dir] = dfs(i + dx[dir], j + dy[dir], (dir + dd[i + dx[dir]][j + dy[dir]] + 4) % 4); vis[i][j][dir] = false; return f[i][j][dir]; } struct CMP{ bool operator()(pair<pii, pii> a, pair<pii, pii> b){ return a.fi.se < b.fi.se || a.fi.se == b.fi.se && a.fi.fi > b.fi.fi; } }; int main(){ cin >> d >> m >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> board[i][j]; if(board[i][j] >= '0' && board[i][j] <= '9') pos[board[i][j] - '1'] = {i, j}, board[i][j] = '.'; if(board[i][j] == 'C') dd[i][j] = 1; if(board[i][j] == 'A') dd[i][j] = -1; } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int dir = 0; dir < 4; dir++){ f[i][j][dir].fi = -2; } } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int dir = 0; dir < 4; dir++){ if(f[i][j][dir].fi == -2) dfs(i, j, dir); } } } // for(int i = 0; i < n; i++){ // for(int j = 0; j < m; j++){ // for(int k = 0; k < 4; k++){ // cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k].fi << ' ' << f[i][j][k].se << endl; // } // } // } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int d1 = 0; d1 < d; d1++){ for(int d2 = d1; d2 < d; d2++){ dp[i][j][d1][d2] = INF; } } } } priority_queue<pair<pii, pii>, vector<pair<pii, pii>>, CMP> q; for(int i = 0; i < d; i++){ for(int j = i; j >= 1; j--){ q.push({{dp[pos[i].fi][pos[i].se][j - 1][i - 1], j - 1}, pos[i]}); } q.push({{0, i}, pos[i]}); while(!q.empty()){ pair<pii, pii> v = q.top(); q.pop(); int cost = v.fi.fi, nd = v.fi.se, x = v.se.fi, y = v.se.se; dp[x][y][nd][i] = cost; for(int dir = 0; dir < 4; dir++){ int nx = f[x][y][dir].fi, ny = f[x][y][dir].se; if(nx == x && ny == y) continue; int co = cost + 1; if(co >= dp[nx][ny][nd][i]) continue; q.push({{co, nd}, {nx, ny}}); for(int j = nd; j >= 1; j--){ if(co + dp[nx][ny][j - 1][nd - 1] >= dp[nx][ny][j - 1][i]) continue; dp[nx][ny][j - 1][i] = co + dp[nx][ny][j - 1][nd - 1]; q.push({{co + dp[nx][ny][j - 1][nd - 1], j - 1}, {nx, ny}}); } } } } int ans = INF; // for(int d1 = 0; d1 < d; d1++){ // for(int d2 = d1; d2 < d; d2++){ // cout << "d " << d1 << ' ' << d2 << endl; // for(int i = 0; i < n; i++){ // for(int j = 0; j < m; j++){ // cout << (dp[i][j][d1][d2] >= INF ? -1 : dp[i][j][d1][d2]) << ' '; // } // cout << endl; // } // } // } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ ans = min(ans, dp[i][j][0][d - 1]); } } cout << (ans >= INF ? -1 : ans) << endl; }

Compilation message (stderr)

robots.cpp: In member function 'bool CMP::operator()(std::pair<std::pair<int, int>, std::pair<int, int> >, std::pair<std::pair<int, int>, std::pair<int, int> >)':
robots.cpp:40:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |   return a.fi.se < b.fi.se || a.fi.se == b.fi.se && a.fi.fi > b.fi.fi;
      |                                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...